This is the 27th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

With a “AVL tree rotation and JS implementation, balance tree branch up ~”, to a difficult, and then a relatively simple, do not always put the “rotating tree” and hit the “binary tree” confidence ~~

Sun arch algorithm! Blunt!

Topic:

Input the root node of a binary tree to determine whether the tree is a balanced binary tree. A binary tree is a balanced binary tree if the depth difference between the left and right subtrees of any node is no more than 1.

Example 1: Given a binary tree [3,9,20, NULL, NULL,15,7] 3 / \ 9 20 / \ 15 7 returns true. Example 2: Given a binary tree [1,2,2,3,3, NULL, NULL,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 returns false.Copy the code
  • Limit: 0 <= Number of nodes in the tree <= 10000

Answer:

To verify whether a binary tree is a balanced binary tree, only the left subtree is a balanced binary tree, the right subtree is a balanced binary tree, and the depth difference between the left and right subtrees is less than 2.

Create depth calculation function:

Detect the incoming tree, if it is empty, return 0, if it is not empty, recursively call the depth calculation function, respectively calculate the depth of the left and right subtrees, return the maximum of the two depths +1 as the result;

Create balance judgment function:

The depth calculation function is used to calculate the depth of left and right subtrees, calculate the depth difference, and recursively call the balance. If the depth difference is less than 2 and both subtrees are balanced, return true, otherwise return false;

Var isBalanced = function(root) {if(! Root){return true} // Calculate the depth difference between left and right subtrees // Determine whether the left and right subtrees are balanced return math. abs(depth(root.left) -depth (root.right)) < 2 && isBalanced(root.left) && isBalanced(root.right) }; /** * depth = function(root) {if(! +1 return math.max (depth(root.left), depth(root.right)) +1}}Copy the code

Think about it the other way around:

There is a lot of double counting above, and you can also use the bottom-up approach:

Create a computational depth function for depth traversal tree:

And right subtree respectively to the left child tree recursive call depth function, calculate the depth, the detecting depth of the left and right subtrees calculation results, if the left subtree of the calculation results of 1, return 1, if the right subtree of the calculation results of 1, return 1, if the depth of the left and right subtrees difference is greater than 1, return 1, detection by, perform follow-up operations;

Take the one with the larger depth value of +1 in the left and right subtrees, return the calculation result, call the calculation depth function, calculate the tree, judge whether the calculation result is -1, if so, the binary tree is unbalanced, if not, the binary tree is balanced;

var isBalanced = function(root) { if(! root){return true} return defs(root) ! = = 1}; Var defs = function(node) {if(! Node) {return 0} // Calculate the left subtree depth const left = defs(node.left) // Calculate the right subtree depth const right = defs(node.right) switch(true) {// Case left === -1: return -1 // If right === -1 case right === -1: Case Math. Abs (left-right) > 1: return-1 default: Return math.max (left, right) + 1}}Copy the code

OK, this is the share ~~

Writing is not easy, please encourage 👍👍👍

I am Anthony Nuggets, the public account of the same name, every day a pawn, dig a gold, goodbye ~