【算法】搜索二叉树，完全二叉树，平衡二叉树的判断---MapleYe

1、概念搜索二叉树(Binary Search Tree - BST)

它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

完全二叉树(Complete Binary Tree- CBT)

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。 经典应用：堆

平衡二叉树(Self-balancing binary search tree)

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 总的一句话就是，任意节点左右子树的高度差不超过1

2、搜索二叉树的判断思路

由于搜索二叉树的特性，根节点 > 左，根节点 < 右，那么其中序遍历的顺序必然是升序的。那么我们只需在中序遍历的非递归版本，每个节点都和上一个节点比较，即可知道整个序列是否有序了。

算法实现 /// 判断是否是搜索二叉树，就要判断是否符合左子树 < 根节点，右子树 > 根节点 /// 而该树是搜索二叉树，那么其中序遍历必然是升序的，因此在非递归的中序遍历基础上 /// 修改，只需对比当前数比上一个数都大，即可判断是否是搜索二叉树 public static boolean isBST(Node head) { if (head == null) { return true; } int pre = Integer.MIN_VALUE; Stack<Node> stack = new Stack<Node>(); while (!stack.isEmpty() || head != null) { if (head != null) { stack.push(head); head = head.left; }else { head = stack.pop(); if (head.value < pre) { return false; } pre = head.value; head = head.right; } } return true; }3、完全二叉树的判断思路

根据完全二叉树排列特性，必然先挂左边的树，可以得出以下结论： 1、如果一个树，有右孩子，没有左孩子，那么必然不是满二叉树 2、如果一个树，只有左孩子，那么后续节点必然都是叶子节点，才能是满二叉树

算法实现

该算法是在层级遍历的基础上，修改的。

/// 判断是否是满二叉树 /// 1、如果一个树，有右孩子，没有左孩子，那么必然不是满二叉树 /// 2、如果一个树，只有左孩子，那么后续节点必然都是叶子节点，才能是满二叉树 public static boolean isCBT(Node head) { if (head == null) { return true; } Queue<Node> queue = new LinkedList<Node>(); queue.offer(head); boolean isLeaf = false; while(!queue.isEmpty()) { head = queue.poll(); if (isLeaf) { if (head.left != null || head.right != null) { return false; } } // 只有右孩子，没有左孩子，必然不是满二叉树 if (head.left == null && head.right != null) { return false; } if (head.left != null && head.right == null) { // 开启后续节点必为叶节点的判断 isLeaf = true; } if (head.left != null) { queue.offer(head.left); } if (head.right != null) { queue.offer(head.right); } } return true; }4、平衡二叉树的判断思路

由于平衡二叉树要求任意左右子树的高度差不超过1。那么，要求当前节点是否平衡，我们需要知道两个信息： 1、该节点的左右子树是否平衡 2、该节点的左右子树高度相差是否大于1 那么，我们就可以根据以上两个条件，知道了我们递归的过程中，需要判断以及返回的东西了

算法实现

在递归求二叉树的高度的基础上，做了修改

public static boolean isBalance(Node head) { boolean[] res = new boolean[1]; res[0] = true; getHeight(head, res); return res[0]; } public static int getHeight(Node head, boolean[] res) { if (head == null) { return 0; } int lh = getHeight(head.left, res); if (!res[0]) { return 0; } int rh = getHeight(head.right, res); if (!res[0]) { return 0; } if (Math.abs(lh - rh) > 1) { res[0] = false; } return Math.max(lh, rh) + 1; } ---来自腾讯云社区的---MapleYe