二叉树的最近公共祖先

二叉树的最近公共祖先

  TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    if (root == nullptr) return nullptr;
    if (root == p || root == q) return root;

    auto left = lowestCommonAncestor(root->left, p, q);
    auto right = lowestCommonAncestor(root->right, p, q);

    if (left == nullptr) return right;
    if (right == nullptr) return left;

    return root;
  }

二叉搜索树的最近公共祖先

  TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    // 确保 p < q
    if (p->val >= q->val) {
      TreeNode *tmp = q;
      q = p;
      p = tmp;
    }

    while (root) {
      if (root->val < p->val) {
        root = root->right;
      } else if (root->val > q->val) {
        root = root->left;
      } else {
        break;
      }
    }
    return root;
  }