Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

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

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 the two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, satisfying 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.Copy the code

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

 

Description:

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

Train of thought

In general, we might go something like this:

  1. First, find two nodes P and Q and their level;
  2. Trace P and Q up to the same level to see if they are equal;
  3. Unequal layer by layer, until the root node can;

However, since this is a binary search tree, which means that all the left nodes are smaller than the root node, and all the right nodes are larger than the root node, we only need recursive judgment:

  1. If both P and Q nodes are smaller than the root node, their nearest common ancestor node is in the left subtree.
  2. If both P and Q nodes are larger than the root node, their nearest common ancestor node is in the right subtree.
  3. And the other cases, it says that either one is in the left subtree and one is in the right subtree, or one is on both sides and one is the root node, and their nearest common ancestor is the root node.

implementation

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}* /
var lowestCommonAncestor = function(root, p, q) {
    if (root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor(root.right, p, q); 
    } else {
        returnroot; }};Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.