“This is the fourth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

[B] [C] [D]

Given a binary tree, determine whether it is a highly balanced binary tree.

In this case, a highly balanced binary tree is defined as:

The absolute value of the height difference between the left and right subtrees of each node in a binary tree is no more than 1.

Example 1:

Input: root = [3,9,20,null,null,15,7] output: trueCopy the code

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4] output: falseCopy the code

Example 3:

Input: root = [] Output: trueCopy the code

Tip:

  • The number of nodes in the tree is in the range[0, 5000] 内
  • -104 <= Node.val <= 104

According to the meaning of the question, if we want to determine whether a tree is a highly balanced binary tree, we need to determine that the absolute value of the height difference between the left and right subtrees for each subtree is not more than 1, so here we carry out this operation through recursion.

The height of each subtree is obtained in the recursion down process, and the height of the left and right subtrees of the current node is obtained in the backtracking process to judge the height difference.

If the height difference is greater than 1, there is a trick to our return value here.

If we return false, then we have to deal with whether the return value is a non-negative integer or false during the backtrace, which brings us additional complexity. Here we can use the trick of returning a maximum value when the height difference is greater than 1 to unify our return value type.

The number of nodes in the tree is in the range of [0, 5000], so return 10000, i.e. double the tree height, to ensure that the number is definitely higher than the normal tree height

So that’s it. Here’s the code

var isBalanced = function(root) {
    function getHeight(root){
        if(root === null) return 0;
        const l = getHeight(root.left),
        r = getHeight(root.right);

        if(Math.abs(l-r)>1) return 10000;
        return Math.max(l,r)+1;
    }
    return getHeight(root)<10000
};
Copy the code

At this point, we are done with leetcode-110-balanced binary tree

If you have any questions or suggestions, please leave a comment!