This is the 28th day of my participation in the August Text Challenge.More challenges in August

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

The most recent common ancestor of binary search trees

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

Description:

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

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

Example:

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.

Thought analysis

You just have to figure out what’s going on in the recursion. Val < node.left. Val < node.val. Val.

There are 4 cases in total:

  1. If the nodes of P and Q are on either side of root, the nearest common ancestor node is root
  2. If p.val or q.val equals root.val, then the nearest common ancestor node is either P or q
  3. P and q are on the same side of root if both cases 1 and 2 are not satisfied:
    • If root.val is greater than p.val and q.val, recurse to the left
    • If root.val is less than p.val and q.val, recurse to the right

Solution 1: JavaScript implementation


/ * * *@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) || (root.val < p.val && root.val > q.val) || root.val === p.val || root.val ===  q.val ) {return root;
  } else if (root.val > q.val) {
    return lowestCommonAncestor(root.left, p, q);
  } else {
    returnlowestCommonAncestor(root.right, p, q); }};Copy the code

Solution 2: C++ implementation

Since js language environment is not provided in the question bank of offer, I used c++ to implement the idea:


class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if( (root->val == p->val) || (root->val == q->val) || (root->val > q->val && root->val < p->val) || (root->val < q->val &&  root->val > p->val) ) {return root;
        } else if (root->val > q->val) {
            return lowestCommonAncestor(root->left, p, q);
        } else {
            return lowestCommonAncestor(root->right, p, q); }}};Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤