判断是否为平衡二叉树

发表于 | 分类于 | 评论数： | 阅读次数： | 阅读次数：

LeetCode 110. Balanced Binary Tree

方法一 （top down）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class solution {
public:
    int depth (TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        return max (depth(root->left), depth(root->right)) + 1;
    }

    bool isBalanced (TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        //计算左右子树的高度
        int depthLeft = depth(root->left);
        int depthRight = depth (root->right);

        return abs(left - right) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
};

使用 depth()函数来计算 树的高度。
在isBalanced()中判断左右子树的高度差（绝对值）是否小于等于1， 并且左右子树也都是平衡二叉树。 这种自顶向下的方法没计算一个点的深度就要把它的所有子代遍历一遍，这样会产生大量的重复计算。

方法二 (bottom up)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isBalanced (TreeNode* root) {
        return DFS(root) != -1;
    }
    int DFS (TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int leftDepth = DFS(root->left);
        if (leftDepth == -1) {
            return -1;
        }
        int rightDepth = DFS(root->right);
        if (rightDepth == -1) {
            return -1;
        }
        if (abs(leftDepth - rightDepth) > 1) {
            return -1;
        }
        return max(leftDepth, rightDepth) + 1;
    }

};

用后序遍历的方式遍历二叉树的每一个节点，在遍历到每一个节点之前就已经遍历了它的左右子树，在遍历每个节点时记录它的深度。（某一节点的深度等于它到叶节点的路径长度）

0%