This is the 22nd day of my participation in the August Wen Challenge.More challenges in August

Finger Offer 68-i. The most recent common ancestor of the binary search tree

The question:

Given a binary search tree, find the most recent common ancestor of two specified nodes in the tree.

The definition of the nearest common ancestor in Baidu Encyclopedia is:

“For two nodes p and Q with root tree T, the nearest common ancestor is expressed as a node X, such that X is the ancestor of P and Q and x is as deep as possible (a node can also be its own ancestor).”

For example, given the following binary search tree: root = [6,2,8,0,4,7,9, null, null, 3, 5)

Example 1:

Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 8 output: 6: node 2 and 8 of recent common ancestor is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 4 output: 2: recent common ancestor node 2, and 4 is 2, because recent common ancestor nodes can be according to the definition for the node itself.

Description:

All nodes have unique values. P and Q are different nodes and exist in the given binary search tree.

Analysis:

  1. First of all, we need to understand that the tree given is a binary search tree, to understand the characteristics of binary search tree

  2. The characteristics of the nearest common ancestor node in binary search tree are analyzed

    Ancestor definition: If pp is in the left (right) subtree of rootroot or p= rootp=root, rootroot is the ancestor of PP.

Definition of nearest common ancestor:

Let node root be a common ancestor of nodes P and q. If its left child node root.left and right child node root.right are not common ancestors of p and Q, root is said to be the “nearest common ancestor”.

According to the above definition, if root is the nearest common ancestor of P and Q, it can only be one of the following:

  1. P and Q are in the subtree of root, and respectively in the different sides of root (i.e. in the left and right subtrees respectively).
  2. P = root, and q is in the left or right subtree of root;
  3. Q = root, and p is in the left or right subtree of root;

Problem solving:

recursively

 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
     if(p.val > root.val && q.val > root.val){
         return lowestCommonAncestor(root.right, p, q);
     }
     if(p.val < root.val && q.val < root.val){
         return lowestCommonAncestor(root.left, p, q);
     }
​
     return root;
 }
Copy the code