DESC:

题目描述

给定一棵二叉树，已知其中没有重复值的节点，请判断该二叉树是否为搜索二叉树和完全二叉树。

示例1

输入
{2,1,3}
返回值
[true,true]
备注:
n≤500000
假设一个二叉搜索树具有如下特征：

    节点的左子树只包含小于当前节点的数。
    节点的右子树只包含大于当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。

百度百科中对完全二叉树的定义如下：

若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）

CODE1:

JAVA:

import java.util.*;/* * public class TreeNode { *   int val = 0; *   TreeNode left = null; *   TreeNode right = null; * } */public class Solution {    /**     *      * @param root TreeNode类 the root     * @return bool布尔型一维数组     */    public boolean[] judgeIt (TreeNode root) {        // write code here        //这个地方用的long型，是防止节点值正好是int型边界，leetcode int是不通过的，牛客可以        boolean isSearchTree = checkSearchTree(root, Long.MIN_VALUE, Long.MAX_VALUE);        boolean isWholeTree = checkWholeTree(root);        return new boolean[]{isSearchTree, isWholeTree};    }        public boolean checkSearchTree(TreeNode node, long min, long max) {            if (node == null) {                return true;            }            //注意这个地方，根据题意，相等为false，所以为>=和<=            if (node.val <= min || node.val >= max) {                return false;            }            return checkSearchTree(node.left, min, node.val) && checkSearchTree(node.right, node.val, max);        }        public boolean checkWholeTree(TreeNode node) {            LinkedList
    
      nodeList = new LinkedList<>();            if (node == null) {                return false;            }            nodeList.offer(node);            while (true) {                TreeNode pop = nodeList.pop();                if (pop == null) {                    break;                }                nodeList.offer(pop.left);                nodeList.offer(pop.right);            }            for (TreeNode nt : nodeList) {                if (nt != null) {                    return false;                }            }            return true;        }}

NOTES1:

搜索树，通过限定左右子树的值域来判断

完全二叉树通过bfs进行判断，层序遍历后，当遇到null时，表明最后一个节点也遍历完了，如果是完全二叉树，那队列剩余的应该都是空节点，否则不是完全二叉树；

CODE2:

import java.util.*;/* * public class TreeNode { *   int val = 0; *   TreeNode left = null; *   TreeNode right = null; * } */public class Solution {    /**     *      * @param root TreeNode类 the root     * @return bool布尔型一维数组     */    public boolean[] judgeIt (TreeNode root) {        // write code here        boolean isSearchTree = checkSearchTree(root, null, null);        boolean isWholeTree = checkWholeTree(root);        return new boolean[]{isSearchTree, isWholeTree};    }        public boolean checkSearchTree(TreeNode node, TreeNode minNode, TreeNode maxNode) {            if (node == null) {                return true;            }            if ((minNode!= null && node.val <= minNode.val) || (maxNode!= null && node.val >= maxNode.val)) {                return false;            }            return checkSearchTree(node.left, minNode, node) && checkSearchTree(node.right, node, maxNode);        }        public boolean checkWholeTree(TreeNode node) {            Queue
    
      queue = new LinkedList<>();            if (node == null) {                return false;            }            queue.offer(node);            boolean flag = false;            //这里循环条件不一样            while (!queue.isEmpty()) {                TreeNode temp = queue.poll();                if (temp == null) {                    flag = true;                    continue;                }                if (flag) {                    //按说已经到尾结点了，后面又有非空节点，说明非完全二叉树                    return false;                }                queue.offer(temp.left);                queue.offer(temp.right);            }            return true;        }}