VIRTUALS

the virtual labs for the virtuals

0%

LeetCode 110. 平衡二叉树

Posted on Edited on In , ,

摘要：
还是和树深度有关。

题目

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树 每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:
给定二叉树 [3,9,20,null,null,15,7]

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回 true 。

示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]

1
2
3
4
5
6
7
      1
     / \
    2   2
   / \
  3   3
 / \
4   4

返回 false 。

二叉树定义:

1
2
3
4
5
6
7
8
9
10
11
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
1
2
3
4
5
6
7
8
9
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

本题绕不开树的高度计算，用到了递归思想（DFS）。从root节点开始向下依次计算每个节点高度，高度为左右孩子节点的高度较大的那个加一，当节点为null时，认为高度为零。

解法一：递归

从root节点开始，比较左右孩子高度差，接着递归比较左右孩子的左右孩子。当出现不平衡条件返回false，一旦某一个子节点出现false，则整个结果是false。
不推荐该方法，因为对于每个节点需要递归计算高度，复杂度太高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); 
    }
    private int height(TreeNode p) {
        if (p == null) {
            return 0;
        }
        return Math.max(height(p.left), height(p.right)) + 1;
    }
}

注意到在计算高度时仍然需要递归，所以这种方法会造成重复遍历。

解法二：自底向上DFS（后序遍历）

在计算高度的同时可以对平衡性进行判断。一旦出现不平衡情况，直接逐层返回一个特殊值。
这是我的原始代码：

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
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (height(root) == -1) {
            return false;
        }
        else {
            return true;
        }
    }
    private int height(TreeNode p) {
        if (p == null) {
            return 0;
        }
        int height_left = height(p.left);
        if (height_left == -1) return -1;
        int height_right = height(p.right);
        if (height_right == -1) return -1;
        if (Math.abs(height_left - height_right) > 1) {
            return -1;
        }
        return Math.max(height_left, height_right) + 1;
    }
}

优化一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }
    private int height(TreeNode p) {
        if (p == null) {
            return 0;
        }
        int height_left = height(p.left);
        if (height_left == -1) {
            return -1;
        }
        int height_right = height(p.right);
        if (height_right == -1) {
            return -1;
        }
        if (Math.abs(height_left - height_right) > 1) {
            return -1;
        }
        return Math.max(height_left, height_right) + 1;
    }
}

三个return -1的情况可以合并：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }
    private int height(TreeNode p) {
        if (p == null) {
            return 0;
        }
        int height_left = height(p.left);
        int height_right = height(p.right);
        if (height_left == -1 || height_right == -1 || Math.abs(height_left - height_right) > 1) {
            return -1;
        }
        return Math.max(height_left, height_right) + 1;
    }
}

可以不用以返回特殊值-1的方式判断不平衡状态，而是定义一个全局变量res：

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
/*
 * 2021-6-25 17:45:51
 * author: etoa
 * 时隔若干月，回头做这道题，一下就用了最优的方法，印象还在。
 */
class Solution {
public:
    bool res = true;
    bool isBalanced(TreeNode* root) {
        dfs(root);
        return res;
    }

    int dfs(TreeNode* node) {
        if (!node) return 0;
        if (!node->left && !node->right) return 1;

        int l = 0, r = 0;
        if (node->left != nullptr) {
            l = dfs(node->left);
            if (!res) return 0;
        }
        if (node->right != nullptr) {
            r = dfs(node->right);
            if (!res) return 0;
        }
        if (abs(r - l) > 1) {
            res = false;
            return 0;
        }
        else {
            return max(l, r) + 1;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    boolean res = true;
    public boolean isBalanced(TreeNode root) {
        if(root==null) return res;
        helper(root);
        return res;
    }
    
    int helper(TreeNode root){
        if(root==null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        
        if(Math.abs(left-right) > 1){
            res = false;
        }
        return Math.max(left,right) + 1;
    }
}

原题链接： LeetCode 110. 平衡二叉树