题解 | #在二叉树中找到两个节点的最近公共祖先#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 
 1. 找到某一个节点的祖先节点序列；
 通过前序遍历，获得指定查找点，并所过的路径节点存放在栈中，其中叶子节点可以出栈；
 划重点：若是左右子节点都遍历完了，就需要将该根节点出栈？为什么
 
 2. 找到两个点的公共祖先节点序列；
 3. 找到最近的公共祖先节点；
 
 */
class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        std::vector<TreeNode*> ancestors;
        std::vector<TreeNode*> o1_path, o2_path;
        VisitCommonAncestor(root, o1, ancestors, o1_path);
        ancestors.clear();
        VisitCommonAncestor(root, o2, ancestors, o2_path);

        auto i = 0;
        TreeNode* lca = nullptr;
        while (i < o1_path.size() && i < o2_path.size()) {
          if (o1_path[i] == o2_path[i])
            lca = o1_path[i];
          
          ++i;
        }

        return lca->val;
    }

    void VisitCommonAncestor(TreeNode* root, int v, std::vector<TreeNode*>& ancestors, std::vector<TreeNode*>& path) {
        if (root == nullptr)
          return;

        ancestors.push_back(root);
        if (root->val == v) {
          path = ancestors;
          return;
        }
          
        VisitCommonAncestor(root->left, v, ancestors, path);
        VisitCommonAncestor(root->right, v, ancestors, path);

        // 当它的左右子树都遍历完之后，就要走当前节点的上一层，所以，需要将当前节点从stack中移除；
        ancestors.pop_back();
    }
};