【 LeetCode 】 235. A binary search tree in recent common ancestor

题目

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先.

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）.”
例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6.

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身.

说明:

所有节点的值都是唯一的.
p、q 为不同节点且均存在于给定的二叉搜索树中.

题解

两次遍历,find path union,The last element of the union is the most recent common ancestor

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */

class Solution {
    
public:
    void search(TreeNode* root,TreeNode* node,vector<TreeNode*> &myvec)
    {
    
        myvec.push_back(root);
        if(root == node)
            return;
        search(node->val < root->val ? root->left : root->right,node,myvec);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
        vector<TreeNode*> vec1;
        vector<TreeNode*> vec2;
        search(root,p,vec1);//cout<<endl;
        search(root,q,vec2);//cout<<endl;
        vector<TreeNode*> result;
        set_intersection(vec1.begin(),vec1.end(),vec2.begin(),vec2.end(),back_inserter(result));
        // for(int i=0;i<result.size();i++)
        // cout<< result[i]->val <<" ";
        // cout<<endl;
        return result.back();
    }
};

一次遍历
在二叉搜索树中,The left child node must be smaller than the ancestor node,The right child node must be greater than the ancestor node
It is when two nodes are located in the left and right subtrees of a node respectively,This node is the nearest common ancestor of these two nodes

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