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 p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

image

<pre style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13px; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: var(--dark-bg); border-color: rgb(51, 51, 51); color: var(--font) !important; padding: 10px 15px; line-height: 1.6; border-radius: 3px; white-space: pre-wrap; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
</pre>

Example 2:

image

<pre style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13px; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: var(--dark-bg); border-color: rgb(51, 51, 51); color: var(--font) !important; padding: 10px 15px; line-height: 1.6; border-radius: 3px; white-space: pre-wrap; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
</pre>

Example 3:

<pre style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13px; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: var(--dark-bg); border-color: rgb(51, 51, 51); color: var(--font) !important; padding: 10px 15px; line-height: 1.6; border-radius: 3px; white-space: pre-wrap; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">Input: root = [1,2], p = 1, q = 2
Output: 1
</pre>

Constraints:

• The number of nodes in the tree is in the range [2, 10<sup>5</sup>].
• -10<sup>9</sup> <= Node.val <= 10<sup>9</sup>
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

---

我的答案：

/**
 * 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:
    unordered_map<TreeNode*, TreeNode*> parent;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        SearchNode(root, p);
        SearchNode(root, q);
        
        vector<TreeNode*> ancestor1, ancestor2;
        
        TreeNode* node1 = p;
        while (node1 != root) {
            ancestor1.push_back(node1);
            node1 = parent[node1];
        }
        ancestor1.push_back(root);
        
        TreeNode* node2 = q;
        while (node2 != root) {
            ancestor2.push_back(node2);
            node2 = parent[node2];
        }
        ancestor2.push_back(root);
        
        int i = 1;
        for (; i<ancestor1.size() and i<ancestor2.size(); ++i) {
            if (*(ancestor1.rbegin()+i) != *(ancestor2.rbegin()+i)) {
                break;
            }
        }
        return *(ancestor1.rbegin()+i-1);
        
    }
    void SearchNode(TreeNode* root_curr, TreeNode* node) {
        if (root_curr == nullptr)
            return;
        if (root_curr != node) {
            if (parent.find(root_curr->left) == parent.end())
                parent[root_curr->left] = root_curr;
            if (parent.find(root_curr->right) == parent.end())
                parent[root_curr->right] = root_curr;
            
            SearchNode(root_curr->left, node);
            SearchNode(root_curr->right, node);
        }
    }
};

Runtime: 36 ms, faster than 10.54% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.
Memory Usage: 22.8 MB, less than 5.07% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.

很慢啊。
我的思路类似235的最初解法

看官方答案：

recursive的默写

class Solution {
public:
    TreeNode* ans = nullptr;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        Search(root, p, q);
        return ans;
    }
    int Search(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr or (p == nullptr and q == nullptr)) return 0;
        
        int sum = 0;
        if (root == p) {
            ++sum;
            p = nullptr;
        }
        if (root == q) {
            ++sum;
            q = nullptr;
        }
        sum += Search(root->left, p, q) + Search(root->right, p, q);
        if (sum == 2 and ans == nullptr) {
            ans = root;
        }
        return sum;
    }
};

Runtime: 12 ms, faster than 99.18% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.
Memory Usage: 14.7 MB, less than 43.79% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.

非常快！

主要思想是，每个节点都有一个值，表示下面有几个p或者q，第一个出现这个值是2的节点就是要找的了

Iterative 的方法

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/

用queue来preorder traverse binary tree，中间过程中记录parent
最后遍历p的parent，只生成p的ancestor，组成一个set，再遍历q的parent，第一个出现在前面set里面的就是LCA