脸面跪经（phone+onsite）

手动赞楼主！！！干烙印！干NDA!

手动支持lz干烙印

感觉A家就是要制衡烙印

Inorder Successor in BST  // 这个有logn^2 的解法？？？？

补充内容 (2017-1-11 05:28):
写错了，是lgn ？

helloworld00 发表于 2017-1-11 05:28
Inorder Successor in BST  // 这个有logn^2 的解法？？？？

补充内容 (2017-1-11 05:28):

显然有啊，你lgn找到目标值，然后他的successor就有两种情况
1 他自己的右子树中最小的
2 若右子树为空，backtrack他爹，他爹的爹，他爹的爹的爹。。直到找到第一个爹把自己当成左子树的，那他爹就是了。找不到说明没有successor。

以上两步合成一个逻辑，就是在自己的右子树  和  比自己的大的爹里面找最小的

1.         static TreeNode findSuccessorInBST(TreeNode root, int target){
   
2.                 TreeNode cur = root;
   
3.                 TreeNode r = null;
   
4.                 while(cur!=null){
   
5.                         if(cur.val==target){
   
6.                                 if(cur.right!=null){
   
7.                                         r = cur.right;
   
8.                                         while(r.left!=null) r = r.left;
   
9.                                 }
   
10.                                 break;
    
11.                         }else if(target<cur.val){
    
12.                                 r = cur;
    
13.                                 cur = cur.right;
    
14.                         }else{
    
15.                                 cur = cur.left;
    
16.                         }  
    
17.                 }
    
18.                 if(cur==null) return null;
    
19.                 return r;
    
20.         }

复制代码

我觉得是design的bar越来越高了。。。。。他们家的算法题都真心不难，可是天马行空的design好难讲！

lc 285
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null) return null;
        if(root.val <= p.val){
            return inorderSuccessor(root.right, p);
        }else{
            TreeNode left = inorderSuccessor(root.left, p);
            return left == null? root: left;
        }
    }
这就是讨论组的第一个高票答案

LZ 求divide two number的logn的解法

shadow算分吗？为啥别人说我的shadow不算分？

lz绝逼被黑了

也请求 two integer division 做法