【基础算法精讲 12】二叉树的最近公共祖先
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(root==null||root==p||root==q){returnroot;}TreeNodeleft=lowestCommonAncestor(root.left,p,q);TreeNoderight=lowestCommonAncestor(root.right,p,q);if(left!=null&&right!=null){returnroot;}// 如果只有左子树找到，就返回左子树的返回值// 如果只有右子树找到，就返回右子树的返回值// 如果左右子树都没有找到，就返回 null（注意此时 right = null）returnleft!=null?left:right;}}235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
思路：需要根据二叉搜索树的性质。 情况1：ifp.val<root.val and q.val<root.val。则需要递归当前节点左子树。 情况2：ifp.val>root.val and q.val>root.val。则需要递归当前节点右子树。 情况3：ifp.val<root.val and q.val>root.val。最近公共祖先就是当前节点。ifp.val>root.val and q.val<root.val。最近公共祖先就是当前节点。ifroot==p or root==q。返回当前节点即可。 ps:为什么这题不需要判断空节点？ 已知题目给出p、q 为不同节点且均存在于给定的二叉搜索树中。那么p和q节点一定存在在树中，并且可以根据当前节点的值和p,q的值提前比对，就能知道p,q是在左子树中，还是在右子树中。而上一题需要判断空节点的原因是，不像本题一样能够提前判断p,q节点在哪颗子树中，可能递归当前子树没有p或者q节点，所以需要判断空节点。 代码：classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){intcur=root.val;if(p.val<cur&&q.val<cur){returnlowestCommonAncestor(root.left,p,q);}if(p.val>cur&&q.val>cur){returnlowestCommonAncestor(root.right,p,q);}returnroot;}}