236. 二叉树的最近公共祖先给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”思路1.当前节点是空节点直接返回空节点2.当前节点是p节点那么返回p节点不需要往下递归。假设当前节点是p节点那么q节点有两种情况一是作为p节点的孩子孙子节点那么它们的公共祖先仍是p节点。二是q节点不和p节点在同一棵子树上那么也没必要往下递归。3.当前节点是q节点那么返回q节点不需要往下递归4.如果p,q节点都在当前节点的左子树那么递归左子树即可只有左子树能找返回递归左子树的结果 如果p,q节点都在当前节点的右子树那么递归右子树即可只有右子树能找返回递归右子树的结果 如果p,q节点分别在当前节点的左子树和右子树那么公共祖先是当前节点。5.如果p,q节点不在当前节点的左右子树返回空节点即可。也就是情况1。 代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } *//** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(rootnull||rootp||rootq){returnroot;}TreeNodeleftlowestCommonAncestor(root.left,p,q);TreeNoderightlowestCommonAncestor(root.right,p,q);if(left!nullright!null){returnroot;}// 如果只有左子树找到就返回左子树的返回值// 如果只有右子树找到就返回右子树的返回值// 如果左右子树都没有找到就返回 null注意此时 right nullreturnleft!null?left:right;}}235. 二叉搜索树的最近公共祖先给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”所有节点的值都是唯一的。p、q 为不同节点且均存在于给定的二叉搜索树中。思路需要根据二叉搜索树的性质。 情况1ifp.valroot.val and q.valroot.val。则需要递归当前节点左子树。 情况2ifp.valroot.val and q.valroot.val。则需要递归当前节点右子树。 情况3ifp.valroot.val and q.valroot.val。最近公共祖先就是当前节点。ifp.valroot.val and q.valroot.val。最近公共祖先就是当前节点。ifrootp or rootq。返回当前节点即可。 ps:为什么这题不需要判断空节点 已知题目给出p、q 为不同节点且均存在于给定的二叉搜索树中。那么p和q节点一定存在在树中并且可以根据当前节点的值和p,q的值提前比对就能知道p,q是在左子树中还是在右子树中。而上一题需要判断空节点的原因是不像本题一样能够提前判断p,q节点在哪颗子树中可能递归当前子树没有p或者q节点所以需要判断空节点。 代码classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){intcurroot.val;if(p.valcurq.valcur){returnlowestCommonAncestor(root.left,p,q);}if(p.valcurq.valcur){returnlowestCommonAncestor(root.right,p,q);}returnroot;}}