Open larscheng opened 5 months ago
先序遍历,根左右,如果q、p等于root,直接返回root
class Solution {
//O(n)/O(n)
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == q || root == p) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null) {
return right;
}
if (right == null) {
return left;
}
return root;
}
}
236. 二叉树的最近公共祖先