每日算法总结——二叉树的判断：二叉搜索树的判断、完全二叉树的判断、满二叉树的判断、平衡二叉树的判断

1、判断一棵二叉树是否是二叉搜索树

• 什么是二叉搜索树？

  二叉搜索树（BinarySearchTree）又叫搜索二叉树，其特点如下：

  1. 每个结点有唯一的值，且每个结点的值均不相同
  2. 若它的左子树不为空，则它的左子树的所有结点均小于根节点的值
  3. 若它的右子树不为空，则它的右子树的所有结点均大于根结点的值
  4. 它的左右子树均为二叉搜索树。

• 如何判断？

  利用二叉树中序遍历，将打印节点的操作换成比较操作即可，可设立一个静态变量preValue用于记录上一个节点的值，若当前节点小于preValue，则认为不满足升序，即不是二叉搜索树。

/**
 * 判断二叉树是否为二叉搜索树BST
 * 利用中序遍历
 */
public static int preValue = Integer.MIN_VALUE;

public static boolean isBinarySearchTree(Node head) {
    if (head == null) {
        return true;
    }
    boolean isBstLeft = isBinarySearchTree(head.left);
    // 当左子树是二叉搜索树，则让上一次遇到的prevalue与cur相比，看是否递增
    if (isBstLeft && preValue <= head.value) {
        preValue = head.value;
        return isBinarySearchTree(head.right);
    } else {
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2、判断一棵二叉树是否是完全二叉树

• 什么是完全二叉树？

  完全二叉树是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1~h-1) 的结点数都达到最大个数 (即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

• 如何判断？

  利用二叉树的宽度优先遍历（层次遍历），在遍历的过程中需要进行以下判断

  1. 对于任一节点，如果它有右孩子，但没有左孩子，则直接返回false
  2. 在条件1不违规条件下，如果遇到了第一个左右孩子不全（即只有左孩子或没有孩子）的节点，则后续的节点都必须是叶节点。

/**
 * 判断一棵二叉树是否为完全二叉树
 */
public static boolean isCompleteBinaryTree(Node head) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(head);
    boolean leaf = false;
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        if ((leaf && (cur.left != null || cur.right != null))||(cur.left == null && cur.right != null)) {
            return false;
        }
        if (cur.left != null) {
            queue.add(cur.left);
        }
        if (cur.right != null) {
            queue.add(cur.right);
        } else {
            leaf = true;
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3、判断一棵树是否是满二叉树

• 什么是满二叉树？

  树的每一层都满的，即：假设树的高为h，节点个数为n，存在关系：2^h-1 = n

• 算法思想：利用递归方法，如果一棵树是满二叉树，则它左孩子和右孩子也是慢二叉树，并且根据左右子树的高度和节点数，可以判断当前树是否是满二叉树。

/**
 * 判断一棵树是否是满二叉树
 * 利用递归
 */
public static boolean isFullBinaryTree(Node root) {
    // 每次递归需要返回：是否是满二叉树、树的高度、树的节点数
    return fbtProcess(root).getKey();
}

public static Pair<Boolean, Pair<Integer, Integer>> fbtProcess(Node root) {
    // Base case
    if (root == null) {
        return new Pair<>(true, new Pair<>(0, 0));
    }
    Pair<Boolean, Pair<Integer, Integer>> pairLeft = fbtProcess(root.left);
    Pair<Boolean, Pair<Integer, Integer>> pairRight = fbtProcess(root.right);
    int height = Math.max(pairLeft.getValue().getKey(), pairRight.getValue().getKey()) + 1;// 本树高度
    int nodeNum = pairLeft.getValue().getValue() + pairRight.getValue().getValue() + 1;// 本树节点总数
    boolean isFull = pairLeft.getKey() && pairRight.getKey() 
        && nodeNum == ((1 << height) - 1);// 本树是否是满二叉树
    return new Pair<>(isFull, new Pair<>(height, nodeNum));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4、判断一棵树是否是平衡二叉树

• 什么是平衡二叉树？

  平衡二叉树又称AVL树，它具有以下几个例子

  1. 可以是空树。
  2. 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。

• 算法思想：利用递归方法，如果一棵树是平衡二叉树，则它的左子树和右子树一定也都是平衡二叉树，且左子树的高度与右子树高度只差不超过 1。

/**
 * 判断一棵二叉树是否是平衡二叉树
 */
public static boolean isAvlTree(Node root) {
    // 递归过程
    return avlProcess(root).getKey();
}

public static Pair<Boolean, Integer> avlProcess(Node root) {
    if (root == null) {
        return new Pair<>(true, 0);
    }
    Pair<Boolean, Integer> pairLeft = avlProcess(root.left);
    Pair<Boolean, Integer> pairRight = avlProcess(root.right);
    // 根据左右子树的信息得到本树的高度和平衡性
    int height = (pairLeft.getValue() + pairRight.getValue()) + 1;
    boolean isBlance = pairLeft.getKey() && pairRight.getKey()
        && Math.abs(pairLeft.getValue() - pairRight.getValue()) <= 1;
    return new Pair<>(isBlance, height);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

总结：解二叉树问题的一般性套路（递归）

• 思想：如果一个问题，可以通过向左孩子、右孩子要信息来解决本树的问题，则一般可以递归化。具体步骤如下：
  1. 判断子树需要返回那些信息（即每次递归返回的信息）。
  2. 根据子树提供的信息，计算出当前整棵树需要返回的信息。
  3. 将计算出的信息返回给父节点。

任何二叉树相关的树型DP问题均可以使用该递归套路解决，比如上面所说的四个问题，其中判断满二叉树和判断平衡二叉树的方法就是用这种递归套路解的，而且判断二叉搜索树问题也是可以用这种套路解题。

使用递归套路判断二叉搜索树

/**
 * 判断二叉树是否为二叉搜索树BST
 * 利用递归套路
 */
public static boolean isBinarySearchTree2(Node root) {
    // 每次递归返回是否是二叉搜索树、树的最大值、树的最小值
    return bstProcess(root).getKey();
}

public static Pair<Boolean, Pair<Integer, Integer>> bstProcess(Node root) {
    // base case
    if (root == null) {
        return null;
    }
    Pair<Boolean, Pair<Integer, Integer>> pairLeft = bstProcess(root.left);
    Pair<Boolean, Pair<Integer, Integer>> pairRight = bstProcess(root.right);
    int max = root.value, min = root.value;
    if (pairLeft != null) {
        max = Math.max(max, pairLeft.getValue().getKey());
        min = Math.min(min, pairLeft.getValue().getValue());
    }
    if (pairRight != null) {
        max = Math.max(max, pairRight.getValue().getKey());
        min = Math.min(min, pairRight.getValue().getValue());
    }
    boolean isSearch = true;
    if (pairLeft != null && (!pairLeft.getKey() || pairLeft.getValue().getKey() > root.value)) {
        isSearch = false;
    }
    if (pairRight != null && (!pairRight.getKey() || pairRight.getValue().getValue() < root.value)) {
        isSearch = false;
    }
    return new Pair<>(isSearch, new Pair<>(max, min));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34