This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

93. Number of complete binary tree nodes (count-complete-tree-nodes)

The label

  • Complete binary tree
  • medium

The title

Leetcode portal

Let’s just open leetCode.

Given the root node of a complete binary tree, find the number of nodes in the tree.

Complete binary trees are defined as follows:

In a complete binary tree, the number of nodes in each layer reaches the maximum except that the lowest node may not be full, and the nodes in the lowest layer are concentrated in the leftmost positions of the layer. If the lowest layer is layer H, this layer contains 1 to 2h nodes.

Input: root = [1,2,3,4,5,6] output: 6Copy the code

The basic idea

If you could just recursively figure out the number of nodes, you could do that, but you’re not going to get the full binary tree property.

If it’s a full binary tree, it looks like this, every level is full of nodes

      1                      
     /  \
    2    3    
   / \  / \
  4   5 6  7  h=3  count = 2^3 - 1
Copy the code

If a full binary tree has a depth of 3, then the number of nodes is 2 ^ 3-1 (2 ^ cubed -1).

2 to the 0 plus 2 to the 1 plus 2 to the 2 so that’s the number of nodes in this layer 1 plus 2 plus 4 is 7

We derive that the number of nodes in the full binary tree is 2^ h-1 and h is the depth of the binary tree

Why is that? Count (h) = 2 ^ 0 (root/layer 1) + 2 ^ 1 (about child/tier 2) + 2 ^ 2 (the third layer node number) +… 2^(h-1) = 1 + 2 + 4 + … 2 ^ (h – 1) out the geometric sequence, geometric sum, a1 = 1, q = 2, S = a1 * (1 – q ^ n)/(1 – q) = 1 * (1-2 h ^)/(1-2) = 2 h ^ 1

So the whole point of doing all this is to get a result, and if it’s a full binary tree, you don’t have to do it recursively, you just have to figure it out.

Writing implement

var countNodes = function(root) {
  if (root == null) {
    return 0;
  }
  // Check whether it is full binary tree, if it is, directly solve the formula
  let [leftHeight, rightHeight] = [0.0]
  let [leftNode, rightNode] = [root, root]
  // If the height of the left and right sides of the tree is the same, then the tree is full
  while(leftNode) {
    leftHeight++
    leftNode = leftNode.left
  }
  while(rightNode) {
    rightHeight++
    rightNode = rightNode.right
  }
  if (leftHeight === rightHeight) {
    return 2 ** leftHeight - 1
  }
  return countNodes(root.left) + countNodes(root.right) + 1; // Add root + 1
};
Copy the code

Lowest-common-ancestor-of-a-binary tree (LOwest-common-ancestor-of-a-binary tree)

The label

  • Binary tree
  • medium

The title

Leetcode portal

Let’s just open leetCode.

Given a binary tree, find the nearest common ancestor of the two specified nodes in the tree.

The definition of the nearest common ancestor in Baidu Encyclopedia is as follows: “For two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, which satisfies that X is the ancestor of P and Q and the depth of X is as large as possible (a node can also be its own ancestor).

Input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, output q = 1:3: node 5 and 1 recent common ancestor node 3.Copy the code

The basic idea

We’re looking for the common ancestor of P and Q, in two cases

  • The current node isroot, p and Q in different subtrees (one on the left and right sides)
  • The current node isroot, p and Q are in the same subtree (both left and right)

Traversal from the root node, recursively query the node information to the left and right subtrees

  • If the nodes found in the left and right subtrees are not empty, it indicates that P and Q are in the left and right subtrees respectively. Therefore, the current node is the nearest common ancestor
  • If one of the left and right subtrees is not empty, a non-empty node is returned becauseBeing returned first indicates being near the root.

Writing implement

var lowestCommonAncestor = function(root, p, q) {
  // When null or p is found, q returns (recursive exit)
  if(! root || root == p || root == q) {return root
  }
  // Recursively traverses the left and right subtrees
  let leftTree = lowestCommonAncestor(root.left, p, q)
  let rightTree = lowestCommonAncestor(root.right, p, q)
  // Scatter over the left and right subtrees and return directly to the root
  if (leftTree && rightTree) {
    return root
  }
  // Or return the first obtained, because the other half of the tree is empty, the first obtained must be the parent of the later
  return leftTree ? leftTree : rightTree;
};
Copy the code

In addition, I would like to recommend the article of the eldest brother to you. It is very simple and profound. It is very effective for the students who advance in the front end. Core concepts and algorithm disassembly series

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me presious tower shock the rever monster, I see it through, the code is not on the ha, add after I will do my best to help you, but pay attention to the way of asking questions, suggest reading this article first: the wisdom of asking questions

reference