leetcode思路-236 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”思路递归解析终止条件当越过叶节点则直接返回 null 当 root 等于 p,q 则直接返回 root 递推工作开启递归左子节点返回值记为 left 开启递归右子节点返回值记为 right 返回值 根据 left 和 right 可展开为四种情况当 left 和 right 同时为空 说明 root 的左 / 右子树中都不包含 p,q 返回 null 当 left 和 right 同时不为空 说明 p,q 分列在 root 的 异侧 分别在 左 / 右子树因此 root 为最近公共祖先返回 root 当 left 为空 right 不为空 p,q 都不在 root 的左子树中直接返回 right 。具体可分为两种情况p,q 其中一个在 root 的 右子树 中此时 right 指向 p假设为 p p,q 两节点都在 root 的 右子树 中此时的 right 指向 最近公共祖先节点 当 left 不为空 right 为空 与情况 3. 同理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; } if(right null){ return left; } return root; }