This article is participating in the nuggets team online activity, clickCheck spring recruitment positions in big factories

I. Title Description:

The most recent common ancestor of binary trees

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).

Example 1:

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

Example 2:

Input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, q = 4 output: 5: node 5 nodes and four recent common ancestor is 5. Because by definition the nearest common ancestor node can be the node itself.Copy the code

Example 3:

Input: root = [1,2], P = 1, q = 2 Output: 1Copy the code

Note:

• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All node.val are different.
• p ! = q
• Both p and q exist in a given binary tree.

Ii. Analysis of Ideas:

** Idea 1: ** recursion

Find the nearest common ancestor node of two child nodes. Tree-related problems start with depth-first and breadth-first traversal. Consider breadth-first traversal as long as the problem indicates that it is handled by hierarchy; Other scenarios, especially those that need to be converted to left and right subtrees, can be considered for depth-first traversal. This problem is traversed in depth.

1. Determine the recursive termination condition:

   if (! root || root == p || root == q) return rootCopy the code

   If root is empty, return root without following the following logic; Root == p or root == q Indicates that the current node root is the parent node.

2. Recurse root.left and root.right to see if these two subtrees have a common parent of P and Q.

   let left = lowestCommonAncestor(root.left, p, q)
   let right = lowestCommonAncestor(root.right, p, q)
   Copy the code

   • If both left and right are null, p and Q are not in the left or right subtree
   • If left is null and right is not null, p and Q are in the right subtree
   • If right is null and left is not null, p and Q are in the left subtree
   • If neither left nor right is null, root is the parent node

Iii. Complete Code:

Idea 1:

var lowestCommonAncestor = function (root, p, q) {
  if(! root || root == p || root == q)return root
  let left = lowestCommonAncestor(root.left, p, q)
  let right = lowestCommonAncestor(root.right, p, q)
  if (left == null && right == null) return null
  if (left == null) return right
  if (right == null) return left
  return root
}
Copy the code

A further variation of this problem is to find the common ancestor node. All you need to do is make a small change in the code above. You can think about it.

Complexity analysis:

• Time complexity: O(N), whichNIs the number of nodes in the binary tree. All nodes of the binary tree can be accessed only once, so the time complexity is O(N).
• Space complexity: O(N), where N is the number of nodes in the binary tree. The stack depth of recursive calls depends on the height of the binary tree, which is at worst a chain with a height of N and thus a space complexity of O(N).

Iv. Summary:

The problem of binary trees starts with depth-first or breadth-first traversal. Finding a common ancestor node in a binary tree uses depth-first traversal.