题目描述 LeetCode 236

输入两个树节点，求它们的最低公共祖先

题目解读

剑指Offer 327
思路一、如果是二叉树，并且是二叉搜索树。
因为二叉搜索树是排序过的，位于左子树的节点都比父节点小，而位于右子树的节点都比父节点大，我们只需要从树的根节点开始和两个输入的节点进行比较。如果当前节点的值比两个节点的值都大，那么最低的共同父节点一定在当前节点的左子树中，于是下一步遍历当前节点的左子节点。如果当前节点的值比两个节点的值都小，那么最低的共同父节点一定在当前节点的右子树中，于是下一步遍历当前节点的右子节点。这样，在树中从上到下找到的第一个在两个输入节点的值之间的节点就是最低公共祖先
思路二、如果这棵树不是二叉搜索树，只是普通的树呢？如果有指向父节点的指针。
这就相当于求两条链表的第一个公共节点
思路三、如果只是普通的二叉树
此时可以遍历二叉树，分别从根节点到输入节点路径，然后在两个路径中从前往后查找，查找到的最后一个公共节点就是最低公共祖先

代码

/**
 * 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:
    bool findPath(TreeNode* root, TreeNode* t, vector<TreeNode* >& v){
        bool flag = false;
        
        // 在节点中加入节点
        v.push_back(root);
        // 如果找到节点，则flag=true，不再往下递归，开始返回
        if(root == t){
            flag = true;
        }
        
        // 左孩子不为NULL，且目前还没找到t，才能通过左子树递归
        if(root->left!=NULL && flag==false){
            flag = findPath(root->left, t, v);
        }
        // 右孩子不为NULL，且已经查完左子树，在左子树中没找到t，
        // 才能沿着右子树递归查找，否则在左子树中找到t，则准备返回
        if(root->right!=NULL && flag==false){
            flag = findPath(root->right, t, v);
        }
        
        // 千万注意这一点，在找到节点t之后，不能再出数组了，
        // 此时数组中保存的是根节点到t的路径(如果没有if则路径依次出栈了，程序出错)
        if(flag == false){
            v.pop_back();
        }
        
        return flag;
    }
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 如果三个节点有一个NULL，则返回NULL
        if(root == NULL || p == NULL || q == NULL){
            return NULL;
        }
        
        vector<TreeNode* > v1;
        vector<TreeNode* > v2;
        // 第一步、找到根节点到两个节点路径
        bool t1 = findPath(root, p, v1);
        bool t2 = findPath(root, q, v2);
        // t1 t2 都为 true 正面在树中找到 p q 
        if(t1==true && t2==true){
            int i=0, j=0;
            TreeNode* tt;
            // 逐步向后比较，找到最后一个相同的节点，即为输入两个节点的最低公共祖先
            while(i < v1.size() && j < v2.size() && v1[i]==v2[j]){
                tt = v1[i];
                i++;
                j++;  
            }
            return tt;
        }
        else{ // 在树中不存在 p q 
            return NULL;
        }
    }
};