Commit ff04075
zjg23
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -8,6 +8,15 @@ | |||
| 8 | 8 | * } | |
| 9 | 9 | */ | |
| 10 | 10 | class Solution { | |
| 11 | + | ||
| 12 | + /** | ||
| 13 | + 注意p,q必然存在树内, 且所有节点的值唯一!!! | ||
| 14 | + 递归思想, 对以root为根的(子)树进行查找p和q, 如果root == null || p || q 直接返回root | ||
| 15 | + 表示对于当前树的查找已经完毕, 否则对左右子树进行查找, 根据左右子树的返回值判断: | ||
| 16 | + 1. 左右子树的返回值都不为null, 由于值唯一左右子树的返回值就是p和q, 此时root为LCA | ||
| 17 | + 2. 如果左右子树返回值只有一个不为null, 说明只有p和q存在与左或右子树中, 最先找到的那个节点为LCA | ||
| 18 | + 3. 左右子树返回值均为null, p和q均不在树中, 返回null | ||
| 19 | + **/ | ||
| 11 | 20 | public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { | |
| 12 | 21 | ||
| 13 | 22 | if(null == root || p == root || q == root) return root; | |
0 commit comments