C++ solution with explanation


  • 0
    H
    bool getHeight(TreeNode *node, int &height) {
        if (node == nullptr) {
            height = 0;
            return true;
        } else {
            int lh = 0, rh = 0;
            if (!getHeight(node->left, lh)) return false;
            if (!getHeight(node->right, rh)) return false;
            height = max(lh, rh) + 1;
            if (lh > rh + 1 || rh > lh + 1) return false;
            return true;
        }
    }
     
    class Solution {
    public:
        bool isBalanced(TreeNode* root) {
            int height = 0;
            return getHeight(root, height);
        }
    };
    

    Function getHeight will update the input parameter height to the height of the sub-tree (with node as root), and this function will return true if the sub-tree (with node as root) is balanced, and return false if is not balanced.

    For each iteration, we will gradually explore to the leaves of the tree. At any point, when the sub-tree is not balanced, we're sure that all the trees containing this sub-tree is not balanced, and then we can safely return false to all the calls above.

    In the function getHeight, we can get the heights of node's two sub-trees, and then get the height of the sub-tree rooted at node. After that, we can check whether the sub-tree rooted at node is balanced or not.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.