236 二叉树的最近公共祖先

https://leetcode.cn/leetbook/read/top-interview-questions-hard/xdh5o7/

cost: 12m01s

/**
 * 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) {
        vector<TreeNode*> ancestors;
        this->walk(root, ancestors, p, q);
        TreeNode* res = nullptr;
        for (int i=0;i<pAncestors.size();i++) {
            if (i<qAncestors.size()) {
                if (pAncestors[i] == qAncestors[i]) {
                    res = pAncestors[i];
                }
            }
        }
        return res;
    }
private:
    void walk(TreeNode* root, vector<TreeNode*>& ancestors, TreeNode* p, TreeNode* q) {
        if (root == nullptr) {
            return;
        }
        ancestors.push_back(root);
        if (root == p) {
            pAncestors = ancestors;
        }
        if (root == q) {
            qAncestors = ancestors;
        }
        this->walk(root->left, ancestors, p, q);
        this->walk(root->right, ancestors, p, q);
        ancestors.pop_back();
    }
    vector<TreeNode*> pAncestors;
    vector<TreeNode*> qAncestors;
};