LC 235和236的解法一样？Lowest Common Ancestor of a BST

一道是Lowest Common Ancestor of a BST, 另一道是Lowest Common Ancestor of a BT, 好像解法一样？另外大家在用分治算法的时候，通常是采用从下往上的方式，还是从上往下？

BST和BT解法的共同点：都根据 if(root ==p || root == q || (rootVal < q.val && rootVal > p.val)) 判断最小公共节点
不同点：BST，根据root值和p，q的比较，决定是继续往左还是往右搜索，直接返回
BT，要搜索左右两棵子树，然后根据返回的值，觉得返回哪个节点。
附上我的具体代码，仅供参考
BST:

1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
   
2.         if(root == null){
   
3.             return null;
   
4.         }
   
5.         
   
6.         if(p.val > q.val){
   
7.             return lowestCommonAncestor(root, q, p);
   
8.         }
   
9.         
   
10.         int rootVal = root.val;
    
11.         if(root ==p || root == q || (rootVal < q.val && rootVal > p.val)){
    
12.             return root;
    
13.         }else if(rootVal > q.val){
    
14.             return lowestCommonAncestor(root.left, p, q);
    
15.         }else{
    
16.             return lowestCommonAncestor(root.right, p, q);
    
17.         }
    
18.         
    
19.         
    
20.     }

复制代码

BT:

1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
   
2.         if(root != null){
   
3.             System.out.println(root.val);
   
4.         }
   
5.         if(root == null || root == p || root == q){
   
6.             return root;
   
7.         }
   
8.         
   
9.         TreeNode left = lowestCommonAncestor(root.left, p, q);
   
10.         TreeNode right = lowestCommonAncestor(root.right, p, q);
    
11.         
    
12.         if(left != null && right != null){
    
13.             System.out.println("Ok" + root.val);
    
14.             return root;
    
15.         }
    
16.         
    
17.         return left == null? right:left;
    
18.     }

复制代码

我用的以下的代码，提交给两道题，都过了：

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if (left != null && right != null) {
            return root;
        }
        if (left != null) {
            return left;
        }
        if (right != null) {
            return right;
        }
        return null;
    }  

235

1.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
   
2.         if(root == p) return p;
   
3.         if(root == q) return q;
   
4.         if(p.val <= root.val && root.val <= q.val || q.val <= root.val && root.val <= p.val) return root;
   
5.         if(p.val <= root.val) return lowestCommonAncestor(root.left, p, q);
   
6.         return lowestCommonAncestor(root.right, p, q);
   
7.     }

复制代码

烦躁.. 所有回复都被审核了..

解法还是不太一样的.. bst看值大小, 二叉树lca得走每一个点
235



236




补充内容 (2018-6-12 06:22):
235 236 弄翻了.. :P