“This is the 12th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Topic link

235. The nearest common Ancestor of binary Search Trees – LeetCode (leetcode-cn.com)

Topic describes

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 as follows: “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).

The test case

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

conditions

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

Subject analysis

We need to find the common ancestor node of two nodes in a binary tree, and this ancestor node is as close as possible to p and Q nodes (that is, we need to find the parent node where P and Q first meet

For a simple gameplay, we walk through the binary tree once, recording the parent nodes of all nodes; Then we iterate over all the parents of the q node and record them in the set. Then we iterate over the parents of the Q node and try to match them in the set

Special cases to consider:

① P may be the first common parent node of the intersection. This is easy to handle. We add p to the set defined earlier

② Q is the first parent node of the intersection. In this case, the parent node traversing Q must not match. We can terminate the traversal search by adding undefined to set, and then return the original q node if the result is undefined after the result is returned

Code implementation

* @param {TreeNode} root * @param {TreeNode} p * @param {TreeNode} q * @return {TreeNode} */ var lowestCommonAncestor = function(root, p, q) { let dq = q; let obj = {}; trave(root); let parents = new Set([p]); while (obj[p.val] ! = undefined) { p = obj[p.val]; parents.add(p) } console.log(obj[p.val],p,obj,parents); while (! parents.has(q)) { q = obj[q.val]; } return q; function trave(root) { if (root.left ! = null) { obj[root.left.val] = root; trave(root.left); } if (root.right ! = null) { obj[root.right.val] = root; trave(root.right); }}};Copy the code

This run was a bit unexpected, but if you look through the code and remove console.log, the results are much more normal

To optimize the

Read the title carefully and find that we need to deal with the binary tree?? In other words, my solution is fairly generic, and if you’re looking for a binary tree to match, it should improve performance even more, so try again next time