朴素解法及优化解法。

朴素解法:

image_up_163896101908229b73.jpg

考虑寻找 0,8 的最近公共祖先。可以先找到各自的路径:

path_p = 3 1 0
path_1 = 3 1 8

然后找到第一对不同的数(0,8)往前的数(1),就是答案。

class Solution {
public:
  void FindPathImpl(stack<TreeNode *> &history, TreeNode *root,
                    TreeNode *target, bool &over) {
    if (over) {
      return;
    }
    history.push(root);
    if (root == nullptr) {
      return;
    }
    if (root == target) {
      over = true;
      return;
    }
    FindPathImpl(history, root->left, target, over);
    if (over) {
      return;
    } else {

      history.pop();
    }
    FindPathImpl(history, root->right, target, over);
    if (over) {
      return;
    } else {

      history.pop();
    }
  }
  deque<TreeNode *> FindPath(TreeNode *root, TreeNode *target) {
    stack<TreeNode *> history;
    bool found = false;
    FindPathImpl(history, root, target, found);
    // reverse
    deque<TreeNode *> ret;
    while (!history.empty()) {
      auto top = history.top();
      history.pop();
      ret.push_back(top);
    }
    return ret;
  }
  TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    auto sp = this->FindPath(root, p);
    auto sq = this->FindPath(root, q);
    auto prev = sp.back();
    while (!sp.empty() && !sq.empty()) {
      if (sp.back() != sq.back()) {
        return prev;
      }
      prev = sp.back();
      sp.pop_back();
      sq.pop_back();
    }
    return prev;
  }
};

执行用时:28 ms, 在所有 C++ 提交中击败了 10.31%的用户 内存消耗:17.2 MB, 在所有 C++ 提交中击败了 5.99%的用户

还有什么办法?

分类讨论:若 p, q 有公共祖先,则:

  1. 要么左右枝各一个
  2. 要么都在同一枝
  TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    // case 1: one in left, another in right
    auto left = lowestCommonAncestor(root->left, p, q);
    auto right = lowestCommonAncestor(root->right, p, q);
    if (left && right) {
      return root;
    }
    // case 2: both in the same side
    auto side = left ? left : right;
    return lowestCommonAncestor(side, p, q);
  }`

好,然后加入终止条件即可:

class Solution {
public:
  TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    if (root == nullptr) {
      return nullptr;
    }
    if (root == p || root == q) {
      return root;
    }
    // case 1: one in left, another in right
    auto left = lowestCommonAncestor(root->left, p, q);
    auto right = lowestCommonAncestor(root->right, p, q);
    if (left && right) {
      return root;
    }
    // case 2: both in the same side
    auto side = left ? left : right;
    return lowestCommonAncestor(side, p, q);
  }
};

还可以写更少,但没必要:

  TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    if (root == nullptr || root == p || root == q) return root;    
    // case 1: one in left, another in right
    auto left = lowestCommonAncestor(root->left, p, q);
    auto right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;
    // case 2: both in the same side
    return lowestCommonAncestor(left ? left : right, p, q);
  }