企业官网建设流程全解析

题目

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出：3解释：节点5和节点1的最近公共祖先是节点3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4输出：5解释：节点5和节点4的最近公共祖先是节点5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2输出：1

提示：

• 树中节点数目在范围[2, 105]内。
• -109 <= Node.val <= 109
• 所有Node.val互不相同。
• p != q
• p和q均存在于给定的二叉树中。

题解

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ 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; if(right == null) return left; return root; } }

思路

从下往上找

1. 递归向左右子树搜索 p、q；
2. 返回值含义：
   • null：该子树既没有 p 也没有 q
   • p/q：该子树找到了 p 或者 q
3. 如果左右返回都不为空：当前节点就是公共祖先；
4. 如果一边为空，返回另一边的非空结果，向上传递；
5. 公共祖先是第一个左、右分别能搜到 p 和 q的节点。