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

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 
 在原来的基础上，添加对VisitCommonAncestor的返回值，以便找到目前节点之后，就可以不用再往下寻找了；
 */
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;
  }

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

    ancestors.push_back(root);
    if (root->val == v) {
      path = ancestors;
      return true;
    }

    if (VisitCommonAncestor(root->left, v, ancestors, path) ||
        VisitCommonAncestor(root->right, v, ancestors, path) ) {
      return true;
    } else {
      ancestors.pop_back(); // 当它的左右子树都遍历完之后，就要走当前节点的上一层，所以，需要将当前节点从stack中移除；
      return false;
    }
  }
};