LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 遍历左右子树，查找 p 和 q，如果在左右子树中各找到一个节点，则该根节点即为最近公共祖先，否则最近公共祖先在某个子树中

class Solution {
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) {
      return root;
    }
    TreeNode* l = lowestCommonAncestor(root->left, p, q);
    TreeNode* r = lowestCommonAncestor(root->right, p, q);
    if (l && r) {  // if ((l == p && r == q) || (l == q && r == p))
      return root;
    }
    return l ? l : r;
  }
};

• 递归过程为前序遍历，时间复杂度 O(n)，过程如下

     3
   /   \
  5     1
 / \   / \
6   2 0   8
   / \
  7   4

查找 5 和 4 的最近公共祖先：
35，找到，不再遍历 5 的子树
108，遍历结束，未找到
3 的左子树返回 5，右子树返回空 => 以 3 为根节点的子树返回 5
结果为 5

查找 6 和 7 的最近公共祖先：
356，找到，不再遍历 6 的子树
27，找到，不再遍历 7 的子树
108，遍历结束，未找到
2 的左子树返回 7，右子树返回空 => 以 2 为根节点的子树返回 7
5 的左子树返回 6，右子树返回 7 => 以 5 为根节点的子树返回 5
3 的左子树返回 5，右子树返回空 => 以 3 为根节点的子树返回 5
结果为 5

查找 2 和 1 的最近公共祖先：
3562，找到，不再遍历 2 的子树
1，找到，不再遍历 1 的子树
5 的左子树返回空，右子树返回 2 => 以 5 为根节点的子树返回 2
3 的左子树返回 2，右子树返回 1 => 以 3 为根节点的子树返回 3
结果为 3