lintcode----最近公共祖先

題目描述：

給定一棵二叉樹，找到兩個節點的最近公共父節點(LCA)。

最近公共祖先是兩個節點的公共的祖先節點且具有最大深度。

注意事項：

假設給出的兩個節點都在樹中存在

樣例：

對于下面這棵二叉樹

LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

思路講解：

由于我們要求祖先，我的第一想法就是将這兩個節點的父親節點全部找出來，然後對其進行查找，找到其相同的節點，然後将其傳回。這樣問題就得到解決了。但是實際做的時候，你會發現不知道怎麼找到某一個節點的父節點，因為兩叉樹是單向的，是以沒有辦法對其子節點比較後，并将其儲存，是以我的解決方法就是 再重建立立一個跟原二叉樹一樣的樹，但是其方向是雙向的，即子節點不僅有指向其左右節點的指針，也有一個指針是指向父親節點的，然後剩下的就好做了，在這個樹中找到兩個待查節點的位置，然後對其進行周遊，将其父親節點全部找到，然後對其進行查找共同節點即可。這裡我用的是儲存了父親節點的值，沒有儲存整個節點，是以後面還要重新查找出原二叉樹中的節點，并将其傳回。

具體代碼：

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


class TreepNode {
  public:
  int val;
  TreepNode *left, *right;
  TreepNode *father;
  TreepNode() {
     this->left = this->right = NULL;
     this->father=NULL;
   }
};


class Solution {
public:
    /*
     * @param root: The root of the binary search tree.
     * @param A: A TreeNode in a Binary.
     * @param B: A TreeNode in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * A, TreeNode * B) { 
        // write your code here
        TreepNode *father_root=new TreepNode();//建立二叉樹的根節點
        father_root->val=root->val;
        father_root->father=NULL;
        father_root->left=NULL;
        father_root->right=NULL;

        TreeNode *head=root;
        TreepNode *father_head=father_root;
        vector<TreepNode*> res;//儲存來兩個待查節點再建立二叉樹的位置

        travel(head,father_head,A,B,res);

        TreepNode * temp=res[];
        vector<int> father_A;
        while(temp!=NULL)
        {
            father_A.push_back(temp->val);
            temp=temp->father;
        }

        temp=res[];
        vector<int> father_B;
        while(temp!=NULL)
        {
            father_B.push_back(temp->val);
            temp=temp->father;
        }
        int flag=;
        int result;
        for(int i=;i<father_A.size();i++)
        {
            for(int j=;j<father_B.size();j++)
            {
                if(father_A[i]==father_B[j])
                {
                    result=father_A[i];
                    goto breakloop;
                }
            }
        }
        breakloop: cout<<"result is "<<result<<endl;

        vector<TreeNode *> p;
        findNode(root,result,p);

        return p[];


    }
    void travel(TreeNode * root,TreepNode * head,TreeNode * A, TreeNode * B,vector<TreepNode *>&res)//重建立立一個雙向的二叉樹
    {
        if(root!=NULL)
        {
            head->val=root->val;

            if(root->left!=NULL)
            {
                head->left=new TreepNode();
                head->left->val=root->left->val;
                head->left->father=head;
            }

            if(root->right!=NULL)
            {
                head->right=new TreepNode();
                head->right->val=root->right->val;
                head->right->father=head;
            }

            travel(root->left,head->left,A,B,res);
            travel(root->right,head->right,A,B,res);

            if(root->val==A->val)
            {
                res.push_back(head);
            }
            if(root->val==B->val)
            {
                res.push_back(head);
            }
        }

    }

    void findNode(TreeNode *root,int result,vector<TreeNode *>&res)//根據具體的值，找到節點
    {
        if(root!=NULL)
        {
            if(root->val==result)
            {
                res.push_back(root);
            }
            findNode(root->left,result,res);
            findNode(root->right,result,res);
        }
    }
};