劍指 Offer 68 - II. 二叉樹的最近公共祖先
后序遍歷
若節(jié)點(diǎn) root 是節(jié)點(diǎn) p 和 q 的最近公共祖先戒幔，則只可能為以下情況之一：
- p 和 q 分別在 root 的左右子樹中
- p = root 洽胶，且 q 在 root 的左或右子樹中
- q = root ，且 p 在 root 的左或右子樹中
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null) return right; // p 和 q 不在左子樹中
if (right == null) return left; // p 和 q 不在右子樹中
return root; // p 和 q 分別在左右子樹
}
}
- 時(shí)間復(fù)雜度 O(n) ：最差情況下软族，需要遞歸遍歷樹的所有節(jié)點(diǎn)连舍。
- 空間復(fù)雜度 O(n) ：最差情況下庶喜，遞歸深度達(dá)到 n 桑寨，需要 O(n) 的額外空間。
