[B] [C] [D]

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.

Their thinking

  1. The binary search tree is traversed to obtain the array of path nodes from the root node to the two target nodes
  2. Traverse the shorter path array from back to front until you find a node that also appears in the other path array, which is the nearest common ancestor node

The demo

Code implementation

var lowestCommonAncestor = function(root, p, q) { let list1,list2; Function preorder(node,list){if(node === null) return; list.push(node); if(node === p){ list1 = list; if(list2) return; } if(node === q){ list2 = list; if(list1) return; } // According to the properties of binary search tree, reduce the search scope if((! list1&&p.val<node.val)||(! list2&&q.val<node.val)){ preorder(node.left,[...list]) } if((! list1&&p.val>node.val)||(! List2&&q.val >node.val) {preOrder (node.right,[...list])}} preOrder (root,[]) // traverses an array of shorter paths from back to front, If (list1.length<list2.length){for(let I = list1.leng-1; let I = list1.leng-1; i>=0; i--){ if(list2.indexOf(list1[i])>-1) return list1[i] } } for(let i = list2.length-1; i>=0; i--){ if(list1.indexOf(list2[i])>-1) return list2[i] } };Copy the code

At this point we are done with leetcode- finger Offer 68-i. The nearest common ancestor of a binary search tree

If you have any questions or suggestions, please leave a comment!