搜索二叉树保存路径法

• 保存路径找出最近公共祖先。
• 找出公共祖先，临界情况分为，第一个不同点，p点，q点。
• 递归函数是if-elseif-else结构，不需要显式return，返回正序顺序，所以先push_back再递归。

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    void getPath(vector<int>& v,int value,TreeNode* root)
    {

        if(root->val==value)
        {
            v.push_back(root->val);
            return;
        }
        else if(root->val<value)
        {
            v.push_back(root->val);
            getPath(v,value,root->right);
        }
        else{
            v.push_back(root->val);
            getPath(v,value,root->left);
        }   
    }
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        if(!root)
        {
            return -1;
        }
        vector<int> p1;
        vector<int>p2;
        getPath(p1, p,root);
        getPath(p2, q,root);
        for(int i=0;i<min(p1.size(),p2.size());i++)
        {
            if(p1[i]!=p2[i])
            {
                return p1[i-1];
            }
        }
        return p1.size()>p2.size()?p2[p2.size()-1]:p1[p1.size()-1];
    }
};

二叉树通用法保存路径

• 非搜索二叉树也适用，上一种方法比，要注意弹出元素，用栈模拟。
• 两个栈只再递归的某一段过程改变，在找到目标元素时，不再更新，因此用引用/全局变量实现避免栈全阶段变化。
• 更通用的方法，但是没有结合搜索二叉树的特点。

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    void recrusion(TreeNode* root, int p, int q, stack<int>& sp, stack<int>& sq) {
        if (!root) {
            return;
        }
        if (sp.empty() || sp.top() != p) {
            sp.push(root->val);
        }
        if (sq.empty() || sq.top() != q) {
            sq.push(root->val);
        }

        recrusion(root->left, p, q, sp, sq);
        recrusion(root->right, p, q, sp, sq);
        if (sp.top() != p) {
            sp.pop();
        }
        if (sq.top() != q) {
            sq.pop();
        }
    }
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        //保存路径
        stack<int> sp;
        stack<int> sq;
        recrusion(root, p, q, sp, sq);
        while (sp.size() > sq.size()) {
            sp.pop();
        }
        while (sp.size() < sq.size()) {
            sq.pop();
        }
        while (sp.top() != sq.top()) {
            sp.pop();
            sq.pop();
        }
        return sp.top();
    }
};

递归法

• 搜索二叉树保证搜索过程是单向的不需要回溯，由上往下。
• 临界分成三种，该节点属于两个节点之一和该节点为p,q的父节点。
• 当根节点不是，则转为从左树节点开始寻找以及从右子树节点开始寻找。
• 向上返回节点值。

int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        if(!root)
        {
            //找不到
            return -1;
        }
        if(root->val==p||root->val==q||(root->val<max(p,q)&&root->val>min(p,q)))
        {
            return root->val;
        }
        else if(root->val>max(p,q))
        {

            return lowestCommonAncestor(root->left, p, q);
        }
        else{
            return lowestCommonAncestor(root->right, p, q);
        }
    }