📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 4853| 回复: 5
跳转到指定楼层
上一主题 下一主题
收起左侧

Lintcode新题 Inorder Successor in BST 怎么做?

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
http://www.lintcode.com/en/problem/inorder-successor-in-bst/

最好有java解法。我搜了这个c++的解法,没有太看明白。

http://www.geeksforgeeks.org/ino ... binary-search-tree/

有思路的同学能给解释一下吗?多谢

上一篇:[Leetcode]听说Word Ladder II是最难的题
下一篇:Permutation II 这个test case 为啥不过呢
推荐
2006reload 2015-10-21 10:17:51 | 只看该作者
全局:
不用那么麻烦

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;
        while(root != null){
            if(p.val < root.val){
                successor = root;
                root = root.left;
            }else{
                root = root.right;
            }
        }
        return successor;
    }
}

评分

参与人数 1大米 +3 收起 理由
Ranged9873 + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

推荐
七夜雪 2015-10-7 02:14:53 | 只看该作者
全局:
我尝试写了一些,不知道能不能通过OJ:
  1. public TreeNode findSuccessor(TreeNode root, TreeNode current){
  2.         if(root==null||current==null)        return null;
  3.         if(current.right!=null){
  4.                 TreeNode next=current.right;
  5.                 while(next.left!=null)
  6.                         next=next.left;
  7.                 return next;
  8.         }
  9.         else{
  10.                 TreeNode node=root, next=null;
  11.                 while(true){
  12.                         if(current.val<node.val){
  13.                                 next=node;
  14.                                 node=node.left;
  15.                         }
  16.                         else if(current.val>node.val)
  17.                                 node=node.right;
  18.                         else
  19.                                 break;
  20.                 }
  21.                 return next;
  22.         }
  23. }
复制代码
主要思路就是两个case:如果这个node有right child,那就在right subtree里找最小的node。如果这个node没有right child,那它的successor肯定是它的某一个Parent,这个case有点难说清,可以画几个图理解一下
回复

使用道具 举报

🔗
温家小猫 2015-10-15 23:21:08 | 只看该作者
全局:
如果p有右孩子,就在右孩子树里找最左点
否则
如果p是parent的左孩子,返回parent
如果p是parent的右孩子,返回p所在第一个左树的parent
  1. if(p.right!=null){
  2.             p=p.right;
  3.             while(p.left!=null){
  4.                 p=p.left;
  5.             }
  6.             return p;
  7.         }
  8.         else{
  9.             TreeNode next=null;
  10.             while(root.val!=p.val){
  11.                 if(p.val<root.val){
  12.                     next=root;
  13.                     root=root.left;
  14.                 }
  15.                 else{
  16.                     root=root.right;
  17.                 }
  18.             }
  19.             return next;
  20.         }
复制代码
回复

使用道具 举报

🔗
yuanb10 2015-10-15 23:23:53 | 只看该作者
全局:
写了个简单粗暴的。。。通关了竟然。。。

public class Solution {
   
   
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        // write your code here
        ArrayList<TreeNode> inList = inOrderTrav(root);
        int ptr = inList.size();
        for (int i = 0; i < inList.size(); i++) {
            if (inList.get(i).equals(p)) {
                ptr = i + 1;
                break;
            }
        }
        
        if (ptr < inList.size()) {
            return inList.get(ptr);
        }
        
        return null;
        
    }
   
    private ArrayList<TreeNode> inOrderTrav(TreeNode root) {
         ArrayList<TreeNode> result = new ArrayList<TreeNode>();
        if (root == null) {
            return result;
        }
        
        ArrayList<TreeNode> left = inOrderTrav(root.left);
        ArrayList<TreeNode> right =  inOrderTrav(root.right);
        result.addAll(left);
        result.add(root);
        result.addAll(right);
        return result;
    }
}

回复

使用道具 举报

🔗
lc19890306 2015-10-16 13:00:37 | 只看该作者
全局:
You do not have permission to access this problem为神马?话说这题跟leetcode里面那个bst iterator方法上有什么本质区别?https://leetcode.com/problems/binary-search-tree-iterator/
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表