04.04. 检查树平衡性

Jul 16, 2020

主要递归函数,计算节点node的深度

    int getDepth(TreeNode* node) {
        if (node == nullptr) return 0;
        return std::max(getDepth(node->left), getDepth(node->right)) + 1;
    }

平衡树对于所有节点有同样的性质:

任意一个节点,其两棵子树的高度差不超过 1。

 bool isBalanced(TreeNode* root) {
        if (!root) return true;
        auto ld = getDepth(root->left);
        auto rd = getDepth(root->right);
        return (std::abs(ld - rd) < 2) 
        && isBalanced(root->left) && isBalanced(root->right);
    }

所以要对每一个子节点递归判断isBalanced

如下图 节点1左右子树深度相同,但是1并不是平衡树

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.