二叉树的最近公共祖先

题目链接：二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

方法一：递归

/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return NULL;
        if (root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);

        if (left && right) return root;
        return left ? left : right;
    }
};

方法二：栈

/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return NULL;
        unordered_map<TreeNode*,TreeNode*> parent;
        parent[root] = NULL;

        stack<TreeNode*> s;
        s.push(root);
        while (!parent.count(p) || !parent.count(q)) {
            TreeNode* cur = s.top();
            s.pop();
            if (cur->left) {
                parent[cur->left] = cur;
                s.push(cur->left);
            }
            if (cur->right) {
                parent[cur->right] = cur;
                s.push(cur->right);
            }
        }
        unordered_set<TreeNode*> se;
        while (p) {
            se.insert(p);
            p = parent[p];
        }
        while (!se.count(q)) {
            q = parent[q];
        }
        return q;
    }
};