递归去找这个结点，如果找到了，就将父元素加到list里面去。
其实就是找到达那个节点的路劲。
这个递归我觉得自己写的很好，巧妙的利用返回值true和false来判断是否将自己加进去。同时在参数里面传list去保存，非常方便。
最后会有两个list，将这两个list，从右往左比较，应该都是相同的元素，第一个不同的元素的上一个元素，就是最先公共祖先。
public class LeetCode236 { public static void main(String[] args) { } public static boolean find(TreeNode node, TreeNode target, LinkedList<TreeNode> queue){ if(node==null) return false; if(node==target){ //因为是包括自己的，自己也能算别人的祖先 queue.add(node); return true; } //左边找到就不去找右边了 //左右孩子如果能找到那个元素，自己就是祖先，把自己加进去 boolean left = find(node.left,target,queue); if(left){ queue.add(node); return true; } boolean right = find(node.right,target,queue); if(right){ queue.add(node); return true; } //左右孩子都没有，那就找不到了 return false; } public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { //获取到达p的路径 LinkedList<TreeNode> list1 = new LinkedList<>(); find(root,p,list1); LinkedList<TreeNode> list2 = new LinkedList<>(); find(root,q,list2); TreeNode last = null; //从右边开始 while (list1.size()!=0&&list2.size()!=0){ //poll是返回队列头部 TreeNode temp1 = list1.pollLast(); TreeNode temp2 = list2.pollLast(); if(temp1==temp2) last=temp1; else break; } return last; } }
其实网上还有更简单的写法。
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { //找到了p或者q的期中一个，或者空了，就返回 //这个只是结束条件而已 if(root == null || root == p || root == q) { return root; } //左子树找 TreeNode left = lowestCommonAncestor(root.left, p, q); //右子树找 TreeNode right = lowestCommonAncestor(root.right, p, q); //如果左右子树都有值，那就是说，p和q都找到了，因为p不可能又在左子树，又在右子树，所以如果一个是p，另一个肯定是q //如果pq在一个结点的左右两侧，那么这个就是最近的了，更高一级的父节点，pq是在一侧的 if(left != null && right != null) { return root; } //如果只找到一个，就返回它自己，因为他代表了到达目标的路径，他能到达目标结点
//在更高一级的结点的时候，就回子递归的结果，因为是最近父结点
return left != null ? left : right; } }
这个解法太巧妙了
每一步，在不同的情况下，都发挥了不同的效果
很难想到
很好的解决了，p或者q本身就是公共结点的情况