[AcWing]72. 平衡二叉树

输入一棵二叉树的根结点，判断该树是不是平衡二叉树。

如果某二叉树中任意结点的左右子树的深度相差不超过 1，那么它就是一棵平衡二叉树。

注意：

  • 规定空树也是一棵平衡二叉树。

数据范围

树中节点数量 [0,500]。

样例

1
2
3
4
5
6
7
8
输入：二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示，
    5
   / \
  7  11
    /  \
   12   9

输出：true

算法思路

在统计二叉树的深度的代码基础上，实时判断当前节点的左右子树的深度差是否大于1，如果是则不是平衡二叉树

代码实现

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // 默认是平衡二叉树，如果判断过程中当前节点的左右子树的深度差大于1，则改为false
    bool res = true;

    int dfs(TreeNode * root){
        // 空树深度为0
        // DFS结束，那层空节点不算深度，返回0
        if(!root) return 0;
        // 如果不是空树,计算当前节点的左右子树深度
        int left = dfs(root -> left);
        int right = dfs(root -> right);
        
        // 如果左右子树深度之差大于1，则不是平衡二叉树
        if(abs(left - right) > 1) res = false;
        // 返回 包括当前节点的，二叉树的深度
        // + 1 是因为当前节点也算1个深度，记得从下往上看

        return max(left, right) + 1;
    }

    bool isBalanced(TreeNode* root) {
        dfs(root);
        return res;
    }
};

注意事项

1
if(abs(left - right) > 1) flag = false; // 为什么这里直接return false是错的

在判断二叉树是否平衡的过程中，如果在递归过程中遇到某个节点的左子树和右子树的高度差大于1，直接返回false确实可以立即表示该树不是平衡的。
但是，你isBalanced函数返回的是 res 啊。你return false只是中断了函数，并没有真的res = false, return res。