方法一： 坐等左边右边来送结果～～～，适合所有二叉树

 

1 class Solution { 2     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 3         if (root == null) { 4             return null; 5         } 6         if (root == p || root == q) { 7             return root; 8         } 9 10         TreeNode left = lowestCommonAncestor(root.left, p, q);11         TreeNode right = lowestCommonAncestor(root.right, p, q);12         if (left != null && right != null) {13             return root;14         }15         if (left != null) {16             return left;17         }18         if (right != null) {19             return right;20         }21         return null;22     }23 }

 

 

方法二 Branch pruning : 

转来自老铁的博客https://home.cnblogs.com/u/davidnyc

 

1  // the goal is to find the root that would sit in the middle 2      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 3          //base case 4          if (root == null) return null ; 5          int min = Math.min(p.val, q.val) ; 6          int max = Math.max(p.val, q.val) ; 7          //pre order：看看当前点是不是满足的值 8          if (root.val>=min && root.val <= max) return root ; 9          //the left: branch pruning > max, then go left： 左边返回就一层层往上返回10          if (root.val > max){11             return lowestCommonAncestor(root.left, p, q) ;12          }13          //the right: branch pruning: