110. Balanced Binary Tree.md

110. Balanced Binary Tree

思路

思路一

一棵非空树是平衡二叉树的充要条件是：

• 其左右子树的高相差不超过1；
• 且左右子树都是平衡二叉树。

因此可考虑用一个递归算法，为此还需要一个递归算法求某树的高。

思路二

思路一的代码十分简洁，但是要注意一个节点会被重复遍历多次因此不是最优的算法。为此我们可以考虑用类似后序遍历的思路，在判断左右子树是否是平衡的同时还需要返回左右子树的高（可以通过传入引用实现），这样就可以不用再递归求左右子树的高了，即整个过程只遍历一遍节点。

C++

思路一

class Solution {
private:
    int getDepth(TreeNode *root){
        if(root == NULL) return 0;
        return 1 + max(getDepth(root -> left), getDepth(root -> right));
    }
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        return (abs(getDepth(root -> left) - getDepth(root -> right)) <= 1) && isBalanced(root -> left) && isBalanced(root -> right);
    }
};

思路二

class Solution {
private:
    bool helper(TreeNode* root, int &height){
        if(!root){
            height = 0;
            return true;
        }
        int l_h = -1, r_h = -1;
        if(helper(root -> left, l_h) && helper(root -> right, r_h)){
            // 此时l_h和r_h已被正确赋值为左右子树的高
            height = 1 + max(l_h, r_h);
            return abs(l_h - r_h) <= 1;
        }
        return false;
    }
public:
    bool isBalanced(TreeNode* root) {
        int height = -1;
        return helper(root, height);
    }
};