题目

截图自官方

代码

解法1：

注意普通二叉树判定最深公共祖先的条件

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { // 没做出来，官方解法1，递归。评论中说： // 这就是一个后序遍历的模型，从下往上，只不过是每个父节点都会接收子节点的状态（是否含有p、q）并把这个状态往上传递，直到该结点满足祖先节点的条件。初次满足的节点，我们判断后将其记录。这样一想就豁然开朗了。且由于我们在最深祖先处返回了true，之上的别的祖先不会在满足修改ans的判断条件了。 // 因为每层递归处理的是“本节点的子树是否含有目标节点中的一个或本节点就是其中一个目标节点”，是的话返回true。 // 题意中有“两个子节点怎么怎么样，我判断怎么怎么样”，一般往后序遍历模型上靠。 TreeNode ans; public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { dfs( root, p, q); return ans; } public boolean dfs(TreeNode root, TreeNode p, TreeNode q){ if(root==null){ return false; } boolean inleftson=dfs( root.left, p, q); boolean inrightson=dfs( root.right, p, q); // 最深公共祖先的判断条件：左右子树同时含有目标节点 // 或者本节点是两个节点中的一个且另一个目标节点在我的左或右子树之中。 // 满足条件的是最深公共祖先 if((inleftson&&inrightson)||((root.val==p.val||root.val==q.val)&&(inleftson||inrightson))){ ans=root; } // 每层递归处理的是“本节点的子树是否含有目标节点中的一个或本节点就是其中一个目标节点”，是的话返回true。 return inleftson||inrightson||(root.val==p.val||root.val==q.val); } }

 

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { // 解法2.用map记录每个节点的父节点，从p或q向上索引，将父节点放入set。从另一个节点向上，找到第一个已经在set中的节点即是。 // 注意记录父节点的手法 Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>(); Set<Integer> visited = new HashSet<Integer>(); public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { dfs(root); while(p!=null){ visited.add(p.val); p=parent.get(p.val); } while(q!=null){ if(visited.contains(q.val)){ return q; } q=parent.get(q.val); } return null; } public void dfs(TreeNode root) { if (root.left != null) { parent.put(root.left.val, root); dfs(root.left); } if (root.right != null) { parent.put(root.right.val, root); dfs(root.right); } } // 都改成TreeNode是一样的 // Map<TreeNode, TreeNode> parent = new HashMap<TreeNode, TreeNode>(); // Set<TreeNode> visited = new HashSet<TreeNode>(); // public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // dfs(root); // while(p!=null){ // visited.add(p); // p=parent.get(p); // } // while(q!=null){ // if(visited.contains(q)){ // return q; // } // q=parent.get(q); // } // return null; // } // public void dfs(TreeNode root) { // if (root.left != null) { // parent.put(root.left, root); // dfs(root.left); // } // if (root.right != null) { // parent.put(root.right, root); // dfs(root.right); // } // } }