一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1952|回复: 5
收起左侧

[算法题] Lintcode新题 Inorder Successor in BST 怎么做?

[复制链接] |试试Instant~ |关注本帖
menderr 发表于 2015-10-6 03:21:58 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

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

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

有思路的同学能给解释一下吗?多谢
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 反对 0

使用道具 举报

七夜雪 发表于 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有点难说清,可以画几个图理解一下
回复 支持 1 反对 0

使用道具 举报

温家小猫 发表于 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/
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 02:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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