[leetcode 236]Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes  5  and  1  is  3 . Another example is LCA of nodes  5  and  4  is  5 , since a node can be a descendant of itself according to the LCA definition.
2つのリーフノードの最初の共通の親ノードを求めます.
まず深さは二叉木全体を優先的に遍歴し,2つのターゲットリーフノードの2つの経路を記録した.
この2つのリーフノードを求める共通の親ノードは、2つのパスを求める最初の共通ノードに相当します.
ACコード:

class Solution
{
public:

    void getList(TreeNode *root,TreeNode *p,TreeNode * q,deque<TreeNode*> &dq1,deque<TreeNode*> &dq2,deque<TreeNode*> &temp)
    {
        if(root==NULL)
            return ;
        else
        {
            temp.push_back(root);
            if(root==p)
                dq1=temp;
            if(root==q)
                dq2=temp;
            getList(root->left,p,q,dq1,dq2,temp);
            getList(root->right,p,q,dq1,dq2,temp);
            temp.pop_back();
        }
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        deque<TreeNode*> dq1;
        deque<TreeNode*> dq2;
        deque<TreeNode*> temp;
        getList(root,p,q,dq1,dq2,temp);

        int sum1=dq1.size();
        int sum2=dq2.size();
        int x=sum1-sum2;
        deque<TreeNode*>::reverse_iterator ite1=dq1.rbegin();
        deque<TreeNode*>::reverse_iterator ite2=dq2.rbegin();
        if(x>0)
            for(int i=0; i<x; ++i)
                ++ite1;
        else
            for(int i=0; i<(-x); ++i)
                ++ite2;
        while(ite1!=dq2.rend())
        {
            if(*ite1==*ite2)
                return *ite1;
            else
            {
                ++ite1;
                ++ite2;
            }
        }
    }
};

  Leetcode  AC  ：https://github.com/PoughER/leetcode