已知二叉樹，求二叉樹中給定的兩個(gè)節(jié)點(diǎn)的最近公共祖先。 最近公共祖先: 兩節(jié)點(diǎn)v與w的最近公共祖先u，滿足在樹上最低(離根最 遠(yuǎn))，且v,w兩個(gè)節(jié)點(diǎn)都是u的子孫。
LeetCode 236. Lowest Common Ancestor of a Binary Tree

思考與分析

1.兩個(gè)節(jié)點(diǎn)的公共祖先一定在從根節(jié)點(diǎn)，至這兩個(gè)節(jié)點(diǎn)的路徑上。
2.由于求公共祖先中的最近公共祖先，那么即同時(shí)出現(xiàn)在這兩條路
徑上的離根節(jié)點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)(或離兩個(gè)最近)。
3.最終算法即:求p節(jié)點(diǎn)路徑，q節(jié)點(diǎn)路徑，兩路徑上最后一個(gè)相同 的節(jié)點(diǎn)。

從根節(jié)點(diǎn)到某節(jié)點(diǎn)路徑（深度搜索）
1.從根節(jié)點(diǎn)遍歷(搜索)至該節(jié)點(diǎn)，找到該節(jié)點(diǎn)后就結(jié)束搜索。
2.將遍歷過程中遇到的節(jié)點(diǎn)按照順序存儲(chǔ)起來(lái)，這些節(jié)點(diǎn)即路徑節(jié)點(diǎn)。
前序遍歷（深度優(yōu)先）

void preorder(TreeNode *node, TreeNode *search){
    if(!node){
        return;
    }
    if(node == search){
        
    }
    preorder(node->left,search);
    preorder(node->right,search);
}

求根節(jié)點(diǎn)至某節(jié)點(diǎn)路徑

void preorder(TreeNode *node,TreeNode *search, std::vector<TreeNode*> &path,std::vector<TreeNode*> &result,int &finish)//node 正在遍歷節(jié)點(diǎn)，search待搜索節(jié)點(diǎn)，path 遍歷時(shí)節(jié)點(diǎn)路徑棧，result 最終搜索到節(jié)點(diǎn)search的路徑結(jié)果，finish 記錄是否找到節(jié)點(diǎn)search的遍歷，未找到時(shí)是0，找到為1{
    if(!node || finish){
    return;//當(dāng)node為空或已找到search 節(jié)點(diǎn)直接返回，結(jié)束搜索
     }
    path.push_back(node);//先序遍歷時(shí)，將節(jié)點(diǎn)壓入path棧
    if(node == search){
        finish = 1;
        result = path;
    }
    preorder(node->left,search,path,result,finish);
    preorder(node->right,search,path,result,finish);
    path.pop_back();//結(jié)束遍歷node時(shí)，將node節(jié)點(diǎn)彈出path棧

}

1.求出較短路徑的長(zhǎng)度n。
2.同時(shí)遍歷p節(jié)點(diǎn)的路徑與q節(jié)點(diǎn)的路徑，遍歷n個(gè)節(jié)點(diǎn)，最后一個(gè)相同節(jié)點(diǎn)，即最近 公共祖先。

class Solution{
public:
    TreeNode* lowestCommonAncestor(TreeNode * root, TreeNode *p ,TreeNode *q){
        std::vector<TreeNode*> path;申明遍歷用的臨時(shí)棧
        std::vector<TreeNode*> node_p_path;//儲(chǔ)存P節(jié)點(diǎn)路徑
        std::vector<TreeNode*>node_q_path;//儲(chǔ)存q節(jié)點(diǎn)路徑
        int finish = 0;//記錄是否完成搜索
        preorder(root, p,path,node_p_path,finish);
        path.clear();//清空path，finish,計(jì)算q節(jié)點(diǎn)路徑
        finish = 0;
        preorder(root, q, path,node_q_path,finish);
        int path_len = 0;
        if(node_p_path.size() < node_q_path.size()){
            path_len = node_p_path.size();
        }
        else{
            path_len = node_q_path.size();
        }
        TreeNode * result = 0;
        for (int i = 0; i < path_len; i++){
            if(node_p_path[i] = node_q_path[i]){
                result = node_p_path[i];
            }//最后相同的節(jié)點(diǎn)為最近公共節(jié)點(diǎn)
        }
        return result;
}
};