“This is the 25th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

The title

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:

Enter: root = [3,9,20,null,null,15,7]

Output: true,

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]

Output: false

Example 3:

Enter: root = []

Output: true,

 

Tip:

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

Their thinking

Method 1: Top-down (brute force method)

Compare the maximum height difference between the left and right subtrees of each node from top to bottom. If the maximum height difference between the left and right subtrees of each node in the binary tree is less than or equal to 1, that is, each subtree is balanced, then the binary tree is a balanced binary tree

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {boolean}* /
var isBalanced = function (root) {
  if(! root)return true
  return Math.abs(depth(root.left) - depth(root.right)) <= 1
        && isBalanced(root.left)
        && isBalanced(root.right)
}
var depth = function (node) {
    if(! node)return -1
    return 1 + Math.max(depth(node.left), depth(node.right))
}
Copy the code

Complexity analysis:

  • Time complexity: O(nlogn), calculationdepthThere are a lot of redundant operations
  • Space complexity: O(n)

Method 2: Bottom-up (optimization)

Use subsequent traversal of the binary tree (left and right roots), return the maximum height of the subtree from bottom to top, determine whether each subtree is balanced, if balanced, use their height to judge whether the parent node is balanced, and calculate the height of the parent node, if not balanced, return -1.

Traversal compares the left and right subtree depth of each node of the binary tree:

Compare the depth of the left and right subtrees. If the difference is greater than 1, return a mark -1, indicating that the current subtree is unbalanced. If the left and right subtrees are balanced, return the depth of the current tree (maximum depth of the left and right subtrees +1).

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {boolean}* /
var isBalanced = function (root) {
    returnbalanced(root) ! = = -1
};
var balanced = function (node) {
    if(! node)return 0
    const left = balanced(node.left)
    const right = balanced(node.right)
    if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
        return -1
    }
    return Math.max(left, right) + 1
}
Copy the code

Complexity analysis:

  • Time complexity: O(n)
  • Space complexity: O(n)

conclusion

This is Xiaokui 🌻, as long as you turn your heart toward the sun, you will have warmth ~

Let’s overcome the algorithm together!!