Complete high-frequency question bank warehouse address: github.com/hzfe/awesom…

The full frequency question bank reading address: febook.hzfe.org/

Topic describes

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.Copy the code

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

Basic knowledge

Each node of a binary tree has at most two child nodes. The height difference between the left and right subtrees of any node in a balanced binary tree cannot be greater than 1. Full and complete binary trees are balanced binary trees, and ordinary binary trees may be balanced binary trees.

Answer key

Method a

Train of thought

To determine whether a binary tree is a balanced binary tree, you only need to determine whether the height difference between the left and right subtrees is less than 1. At the same time, for a tree to be a balanced binary tree, its subtrees must also be balanced binary trees. We can start from the root, recursively calculate the height of the subtree, and whether the subtree is a balanced binary tree, so as to judge whether the binary tree is a balanced binary tree.

code

/** * 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} */ const isBalanced = function (root) { if (root === null) { return true; } else { return ( Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right) ); }}; const height = function (root) { if (root === null) { return 0; } else { return Math.max(height(root.left), height(root.right)) + 1; }};Copy the code

Time complexity analysis

The worst-case scenario is that each parent node has only one child node, so that the height time complexity of the tree is O(n), the length of the “linked list”. The time complexity of calling height function at layer D is O(d), so the overall time complexity is high time complexity * the time complexity of calling height function, namely O(n^2).

Spatial complexity analysis

Since this method uses recursion and calls itself twice each time, the function stack will be opened up according to arithmetic sequence, so the spatial complexity of this method should be O(n^2).

Method 2

Train of thought

The above method is top-to-top, which in effect causes the height of each layer to be counted twice. Then, we can use a back-order traversal so that the height of each node can be calculated from the previous result.

code

/**
 * 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) {
  return height(root) != -1;
};

var height = function (root) {
  if (root == null) {
    return 0;
  }

  const left = height(root.left);
  const right = height(root.right);

  if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
    return -1;
  }

  return Math.max(left, right) + 1;
};

Copy the code

Time complexity analysis

Since it is a back-order traversal, each node is called only once, so the time complexity of this method is O(n).

Spatial complexity analysis

Since this method uses recursion and calls itself twice each time, the function stack will be opened up according to arithmetic sequence, so the spatial complexity of this method should be O(n^2).