蔚来汽车面试真题解析-算法篇-59-判断一棵二叉树是否为搜索二叉树和完全二叉树
试题描述：
给定一棵二叉树，已知其中的节点没有重复值，请判断该二叉树是否为搜索二叉树和完全二叉树。
输出描述：分别输出是否为搜索二叉树、完全二叉树。
数据范围：二叉树节点数满足0≤n≤500000 ，二叉树上的值满足 0≤val≤100000
要求：空间复杂度 O(n)，时间复杂度 O(n)
注意：空子树我们认为同时符合搜索二叉树和完全二叉树。
示例
输入：
{2,1,3}
返回值：
[true,true]
靓丽分割线
参考答案：
第一种解决方案：递归+广度优先遍历
解题思路：
搜索树：使用递归的方式进行求解，判断该二叉树的左子树不为空，则左子树上所有节点的值均小于的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。
完全树：使用宽度优先进行遍历求解，判断遇到左右孩子不双全的节点并且该节点不是叶子节点，不是完全二叉树；当遇到节点的左孩子为空且右孩子不为空的时候，不是完全二叉树；
参开代码如下：
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 hereboolean[] res = new boolean[2];res[0] = isSerachTreeBST(root, Long.MIN_VALUE, Long.MAX_VALUE);res[1] = isAllTreeBST(root);return res;}//判断搜索树public boolean isSerachTreeBST(TreeNode root, long left, long right){if(root == null)return true;if(root.val <= left || root.val >= right)return false;return isSerachTreeBST(root.left, left, root.val) && isSerachTreeBST(root.right, root.val, right);}//判断完全树public boolean isAllTreeBST(TreeNode root){if(root == null) return true;Deque<TreeNode> queue = new LinkedList<>();queue.offer(root);TreeNode left = null;TreeNode right = null;boolean flag = false; //标记是否遇到节点不双全的节点while(!queue.isEmpty()){root = queue.poll();left = root.left;right = root.right;//遇到左右孩子不双全的节点并且该节点不是叶子节点的时候就不是完全二叉树 //左孩子为空并且右孩子不为空的时候不是完全二叉树if((flag && !(left == null && right == null)) || (left == null && right != null)){return false;}if(left != null) queue.offer(left);if(right != null) queue.offer(right);if(left == null || right == null) flag = true;}return true;}}
复杂度分析：
时间复杂度：O(N) n 为二叉树的节点数。
空间复杂度：O(N) 搜索树和完全树申请了两次空间
第二种解决方案：中序遍历+广度优先遍历
解题思路：
搜索树：中序遍历时，判断当前节点是否大于中序遍历的前一个节点，如果大于，说明满足 搜索树，继续遍历；否则直接返回 false。
完全树：使用宽度优先进行遍历求解，判断遇到左右孩子不双全的节点并且该节点不是叶子节点，不是完全二叉树；当遇到节点的左孩子为空且右孩子不为空的时候，不是完全二叉树；
参考代码如下：
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 hereboolean[] res = new boolean[2];res[0] = isSerachTreeBST(root);res[1] = isAllTreeBST(root);return res;}long pre = Long.MIN_VALUE;//判断搜索树public boolean isSerachTreeBST(TreeNode root){if(root == null)return true;// 访问左子树if (!isSerachTreeBST(root.left)) {return false;}// 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。if (root.val <= pre) {return false;}pre = root.val;// 访问右子树return isSerachTreeBST(root.right);}//判断完全树public boolean isAllTreeBST(TreeNode root){if(root == null) return true;Deque<TreeNode> queue = new LinkedList<>();queue.offer(root);TreeNode left = null;TreeNode right = null;boolean flag = false; //标记是否遇到节点不双全的节点while(!queue.isEmpty()){root = queue.poll();left = root.left;right = root.right;//遇到左右孩子不双全的节点并且该节点不是叶子节点的时候就不是完全二叉树 //左孩子为空并且右孩子不为空的时候不是完全二叉树if((flag && !(left == null && right == null)) || (left == null && right != null)){return false;}if(left != null) queue.offer(left);if(right != null) queue.offer(right);if(left == null || right == null) flag = true;}return true;}}
复杂度分析：
时间复杂度：O(N) n 为二叉树的节点数。
空间复杂度：O(N) 搜索树和完全树申请了两次空间