LeetCode236 二叉树的最近公共祖先

链接: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

题意

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

解法

核心思想还是dfs
每次处理左节点和右节点
如果两者分别包含p或者q
则root一定是lca
否则返回左右节点中同时包含p和q的节点

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr) return nullptr;
if (root == p || root == q) return root;
TreeNode* l = lowestCommonAncestor(root -> left, p, q);
TreeNode* r = lowestCommonAncestor(root -> right, p, q);
if (l && r) return root;
return l ? l : r;
}
};