Leetcode面试经典150题-236.二叉树的最低公共祖先
解法都在代码里，不懂就留言或者私信
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {/**题目分析：本题是经典的二叉树的递归套路问题我们要找的是最低的既包含p又包含q的树，首先是这颗树要包含p和q然后是最低，有几种情况：1. 当前树的左树有p（或者q），右树有q和p2. 当前树的根节点就是p(或者q)，然后它的左孩子或者右孩子包含q(或者p)如果某个子树已经包含他们的公共祖先了就一路传递到root所有我们对于每棵树是需要以下信息：1. 是否包含p2. 是否包含q3. p和q的公共祖先是谁（有就设置，没有就为null）把这三个信息定义成Info类，最后拿到root然后拿到公共祖先这个值就行了*/public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {Info info = getInfo(root, p, q);return info.lowestCommonAncestor;}public Info getInfo(TreeNode root, TreeNode p, TreeNode q) {/**关于空节点的特殊处理，这里不返回null，不然后面的非空判断太多 */if(root == null) {return new Info(false, false, null);}/**拿到左右孩子的Info信息 */Info leftInfo = getInfo(root.left,p,q);Info rightInfo = getInfo(root.right,p, q);/**这里我做个优化，如果左右孩子已经包含最低公共祖先了，那其他信息也不重要了，把最低公共最先已经传到到树的根上就行了 */if(leftInfo.lowestCommonAncestor != null || rightInfo.lowestCommonAncestor != null) {return new Info(true, true, leftInfo.lowestCommonAncestor != null? leftInfo.lowestCommonAncestor : rightInfo.lowestCommonAncestor);}/**下面定义当前root的Info三个属性 *//**自己是p或者左右孩子包含p就是包含 */boolean containsP = root == p || leftInfo.containsP || rightInfo.containsP;/**自己是q或者左右孩子包含q就是包含 */boolean containsQ = root == q || leftInfo.containsQ || rightInfo.containsQ;/**判断当前树有没有p和q的祖先:1.左右某个子树包含最低公共祖先 2.当前节点是p(q)，子树包含q(p) 3.左子树包含p(q)，右子树包含q(p)方法开头的优化我们已经判断了某个子树包含最低公共祖先的情况，也就是我们只需要判断2，3就行了*/TreeNode lowestCommonAncestor = (root == p && (leftInfo.containsQ || rightInfo.containsQ)) || (root == q && (leftInfo.containsP || rightInfo.containsP))|| (leftInfo.containsP && rightInfo.containsQ) || (leftInfo.containsQ && rightInfo.containsP)? root : null;return new Info(containsP, containsQ, lowestCommonAncestor);}static class Info {boolean containsP;boolean containsQ;TreeNode lowestCommonAncestor;public Info(boolean containsP, boolean containsQ, TreeNode lowestCommonAncestor) {this.containsP = containsP;this.containsQ = containsQ;this.lowestCommonAncestor = lowestCommonAncestor;}}
}运行结果：
