题目给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 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 ! qp和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; } }思路从下往上找递归向左右子树搜索 p、q返回值含义null该子树既没有 p 也没有 qp/q该子树找到了 p 或者 q如果左右返回都不为空当前节点就是公共祖先如果一边为空返回另一边的非空结果向上传递公共祖先是第一个左、右分别能搜到 p 和 q的节点。