This is the 20th day of my participation in the August Text Challenge.More challenges in August

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

[LeetCode 110. Balanced binary tree] Two recursive implementations: top down and bottom up

Topic describes

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 of a binary tree is no more than 1.

Solution 1: Top down

The definition of a radical balanced binary tree, which can recursively compare the height difference between the left and right subtrees of each node, whether more than 1. If all nodes meet the conditions, then it is a balanced binary tree; Otherwise, it’s not a balanced binary tree.

The code implementation is as follows:

var isBalanced = function(root) {
  if(! root)return true;
  return (
    isBalanced(root.left) &&
    isBalanced(root.right) &&
    Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1
  );
};

/** * Get the height of the binary tree *@param {TreeNode} root
 * @return {number}* /
function maxDepth(root) {
  if(! root)return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
Copy the code
Solution 2: Bottom up (recommended)

You may already see the problem with solution 1: the height of each node is double-counted. This introduces additional time consumption. So how do you avoid these double calculations?

The solution is: first calculate whether the left and right subtrees are balanced binary trees, and calculate and save the height of the left and right subtrees, then the height of the current binary tree can be directly calculated by the height of the left and right subtrees.

In JavaScript, saving the result of a calculation during the process is simple: you can pass an object as a parameter with the attribute depth, which represents the height of the binary tree with the current node as the root.


var isBalanced = function(root, obj = {}) {
  if(! root) { obj.depth =0;
    return true;
  }

  const left = {}; // Left subtree information
  const right = {}; // Right subtree information
  if (isBalanced(root.left, left) && isBalanced(root.right, right)) {
    if (Math.abs(left.depth - right.depth) > 1) {
      // Check the height difference between left and right subtrees
      return false;
    }

    obj.depth = Math.max(left.depth, right.depth) + 1; // The current height of the binary tree
    return true;
  } else {
    return false; }};Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤