判断是否为平衡二叉树

发表于 阅读次数：

题目 平衡二叉树

leetcode-110号题，给定一个二叉树，判断它是否是高度平衡的二叉树。

  • 平衡二叉树的定义：

    一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1

  • 例子：

    • 给定二叉树 [3,9,20,null,null,15,7]
1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回true。

思路

这种类型的题目还是比较好做的，我们有许多种类的二叉树，大多都是当前树与其子树之间有着某种关系。只要把节点进行比对就可以判断了。回忆一下，我们利用了递归实现了二叉树的前中后序遍历。

  • 在递归的过程中，每一个节点都会经过3次。这样就可以对比父子节点了

下面来分析一下，以X节点为头的树要判断是否为平衡二叉树需要如下：

  1. 其左子树是否平衡

  2. 其右子树是否平衡

  3. 左子树的高和右子树的高（判断高度差）

实现

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
35
36
37
38
39
40
41
42
43
44
45
46
47
public static boolean isBalance(Node head) {

        /**
         * getLevel(Node head, int level, boolean[] res)
         *
         * 此处的level每一层都会加一，那我从左子树到右子树递归的话，右子树的层数就会有错（当X的左子树level为3，那么X的右节点的level就是4了，正常来说是2）,所以用基本类型作为形参
         * 但res是每一个子树都要公用的，所以用引用类型来修改同一块内存
        **/
        boolean[] res = {true};
        getLevel(head, 1,res);
        return res[0];
    }

    public static int getLevel(Node head, int level, boolean[] res) {

        if(head == null) return level;
        //1. 其左子树是否平衡
        int left = getLevel(head.left, level + 1, res);
        //如果有其中一个不平衡了，随便返回啦，gkd
        if(!res[0]) {
            return level;
        }
        //2. 其右子树是否平衡
        int right = getLevel(head.right,level + 1, res);
        if(!res[0]) {
            return level;
        }

        //3. 比较左子树的高和右子树的高（判断高度差）
        if(Math.abs(left - right) > 1)
        {
            res[0] = false;
        }
        //正常情况下取左右子树层数较高者
        return Math.max(left, right);
    }


    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.left.left = new Node(3);
        head.left.left.left = new Node(4);
        head.right = new Node(7);

        System.out.println(isBalance(head));
    }