Balanced Binary Tree#

Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth difference of every node's two subtrees is not more than 1.

Example#

Solution#

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    var target = true;
    var dfs = function(root){
        if(!root) return 0;
        if(!target) return 0;
        var l = dfs(root.left);
        var r = dfs(root.right);
        if(Math.abs(l-r)>1) target = false;
        return l > r ? l+1 : r+1;
    }
    dfs(root);
    return target;
};

Idea#

Define a function for deep recursive traversal. Obtain the heights of the left and right subtrees of a node, in other words, define a function to obtain the height of the tree. When obtaining the heights of the left and right subtrees, compare whether the left and right subtrees are balanced. First, define the target variable target, and then define the deep recursive traversal dfs function. In the function, if the node does not exist, return 0. Then comes the pruning part. If an unbalanced position has already been found, there is no need to continue traversing down. After that, define l as the height of the left subtree, r as the height of the right subtree, then compare, if the height difference between the left and right subtrees is greater than 1, then it is deemed as not a balanced binary tree, assign target to false, and then return the height of the higher subtree of the left and right subtree +1, execute dfs deep recursive traversal, and return target when done.

Daily Question#

Reference#