<p>Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.</p>

<p>According to the <a href="https://en.wikipedia.org/wiki/Lowest_common_ancestor" target="_blank">definition of LCA on Wikipedia</a>: &ldquo;The lowest common ancestor is defined between two nodes <code>p</code> and <code>q</code> as the lowest node in <code>T</code> that has both <code>p</code> and <code>q</code> as descendants (where we allow <b>a node to be a descendant of itself</b>).&rdquo;</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/14/binarytree.png" style="width: 200px; height: 190px;" />
<pre>
<strong>Input:</strong> root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
<strong>Output:</strong> 3
<strong>Explanation:</strong> The LCA of nodes 5 and 1 is 3.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/14/binarytree.png" style="width: 200px; height: 190px;" />
<pre>
<strong>Input:</strong> root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
<strong>Output:</strong> 5
<strong>Explanation:</strong> The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> root = [1,2], p = 1, q = 2
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

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

/**
 * 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:
    void inorder(TreeNode* root, vector<int>& v) {
        if (root == NULL) return;
        inorder(root->left, v);
        v.push_back(root->val);
        inorder(root->right, v);
    }

    void preorder(TreeNode* root, vector<int>& v) {
        if (root == NULL) return;
        v.push_back(root->val);
        preorder(root->left, v);
        preorder(root->right, v);
    }

    TreeNode* findNode(TreeNode* root, int value) {
        if (root == NULL) return NULL;
        if (root->val == value) return root;
        TreeNode* left = findNode(root->left, value);
        if (left) return left;
        return findNode(root->right, value);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<int> pre, in;
        inorder(root, in);
        preorder(root, pre);

        int pi = p->val, qi = q->val;
        auto pre_pi = find(pre.begin(), pre.end(), pi);
        auto pre_qi = find(pre.begin(), pre.end(), qi);

        if (pre_pi == pre.end() || pre_qi == pre.end()) return NULL;

        int c = distance(pre.begin(), pre_pi);
        int d = distance(pre.begin(), pre_qi);
        int j = min(c, d);

        auto in_pi = find(in.begin(), in.end(), pi);
        auto in_qi = find(in.begin(), in.end(), qi);

        if (in_pi == in.end() || in_qi == in.end()) return NULL;

        int a = distance(in.begin(), in_pi);
        int b = distance(in.begin(), in_qi);

        if (a > b) {
            swap(a, b);
        }

        for (int i = 0; i <= j; i++) {
            for (int k = a; k <= b; k++) {
                if (in[k] == pre[i]) {
                    return findNode(root, pre[i]);
                }
            }
        }

        return NULL;
    }
};

17200