一亩三分地论坛

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

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

Print value in a given range of BST tree.

[复制链接] |试试Instant~ |关注本帖
blackrose 发表于 2016-6-7 04:37:53 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Microsoft - Other - Onsite |Otherfresh grad应届毕业生

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

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

x
问大家刚刚面试微软的题: print value in a given range of BST, dont use recursion
struct TreeNode {
   int val;
   TreeNode* left;
   TreeNode* right;
};.1point3acres缃
. from: 1point3acres.com/bbs
这个题如果不用recursion的话,只能想到 或者 in-order traversal 把node值全都存下来,或者 bfs,但是用bfs的话,就不用BST 这个feature了。。。不了解面试官要考什么? 大家有其他方法么?

评分

1

查看全部评分

jy_121 发表于 2016-6-7 04:52:32 | 显示全部楼层
就是遍历时利用BST的性质和区间的关系,使得时间优于O(n)?
回复 支持 反对

使用道具 举报

 楼主| blackrose 发表于 2016-6-7 04:53:48 | 显示全部楼层
jy_121 发表于 2016-6-7 04:52-google 1point3acres
就是遍历时利用BST的性质和区间的关系,使得时间优于O(n)?

咋遍历? bfs 的话,肯定不行阿。。。。
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-6-7 05:08:34 | 显示全部楼层
blackrose 发表于 2016-6-7 04:53
. 鍥磋鎴戜滑@1point 3 acres咋遍历? bfs 的话,肯定不行阿。。。。

这样?不知道我是否理解题意

. 鍥磋鎴戜滑@1point 3 acres

补充内容 (2016-6-7 05:08):
public static void find(TreeNode root, List<Integer> l, int start, int end){. From 1point 3acres bbs
                if(root == null){
                        return;
                }
                else if(root.val > end){
                        find(root.left,l,start,end);
                }
                else if(root.val < s...
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-6-7 05:09:21 | 显示全部楼层
public static void find(TreeNode root, List<Integer> l, int start, int end){
                if(root == null){
                        return;
                }
                else if(root.val > end){
                        find(root.left,l,start,end);
                }
                else if(root.val < start){
                        find(root.right,l,start,end);
                }
                else{
                        l.add(root.val);
                        find(root.left,l,start,root.val);
                        find(root.right,l,root.val,end);
                }
               
        }
回复 支持 反对

使用道具 举报

 楼主| blackrose 发表于 2016-6-7 05:16:38 | 显示全部楼层
jy_121 发表于 2016-6-7 05:09. Waral 鍗氬鏈夋洿澶氭枃绔,
public static void find(TreeNode root, List l, int start, int end){
                if(root == null){. 鍥磋鎴戜滑@1point 3 acres
                        return; ...
. more info on 1point3acres.com
no recursion....
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-6-7 05:26:39 | 显示全部楼层

哦哦,不好意思,没注意到。这样用个stack就行了吧?
回复 支持 反对

使用道具 举报

 楼主| blackrose 发表于 2016-6-7 06:03:49 | 显示全部楼层
脑子进shi了。。。。。写出来了。。。fuc
.鐣欏璁哄潧-涓浜-涓夊垎鍦
void printNode(root) {
  stack<Node*> nodes;
  while(!root || !nodes.empty()) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
    if(root) {
      nodes.push(root);
      Node* tmp = nodes.top();. from: 1point3acres.com/bbs
      if(tmp->val < small && tmp->val > big) {}
      else {
.鐣欏璁哄潧-涓浜-涓夊垎鍦        root = root->left;
      }
    } else {
      Node* top = stack.top();
      stack.pop();. 鍥磋鎴戜滑@1point 3 acres
      if(top->val >= small && top->val <= big) cout << tp->val << endl;. 1point3acres.com/bbs
      if(top->right) root = top->right;
    }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  }
}
回复 支持 反对

使用道具 举报

youto 发表于 2016-6-7 06:50:52 | 显示全部楼层
input是(root,min,max)吗?
回复 支持 反对

使用道具 举报

 楼主| blackrose 发表于 2016-6-7 07:47:58 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

 楼主| blackrose 发表于 2016-6-7 07:48:11 | 显示全部楼层
youto 发表于 2016-6-7 06:50
input是(root,min,max)吗?

shi
回复 支持 反对

使用道具 举报

chaochao180 发表于 2016-6-9 00:22:45 | 显示全部楼层
blackrose 发表于 2016-6-7 06:03
脑子进shi了。。。。。写出来了。。。fuc

void printNode(root) {

没看明白,你前面定义的stack名字叫nodes,后面用stack了?还有中间if(tmp->val < small && tmp->val > big){}这里2个条件不可能同时成立啊。
回复 支持 反对

使用道具 举报

 楼主| blackrose 发表于 2016-6-9 00:38:53 | 显示全部楼层
当然不能运行,就个大概的意思。。。。把if条件分开 分别在left 和right 就可以了。
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-9 01:41:48 | 显示全部楼层
  1. public List<Integer> inorderTraversal(TreeNode root, int max , int min) {
  2.         List<Integer> rst = new ArrayList<Integer>();
  3.         while (root != null) {
  4.             if (root.left == null) {
  5.                 if (min<root.val&&root.val<max)rst.add(root.val);
  6.                 root = root.right;
  7.             } else {
  8.                 TreeNode run = root.left;
  9.                 while (run.right != null && run.right != root)
  10.                     run = run.right;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  11.                 if (run.right == null) {
  12.                     run.right = root;
  13.                     root = root.left; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  14.                 } else {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  15.                     run.right = null;.1point3acres缃
  16.                     if (min<root.val&&root.val<max)rst.add(root.val);
  17.                     root = root.right;
  18.                 }
  19.             }
  20.         }
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  21.         return rst;
  22.     }
复制代码
回复 支持 反对

使用道具 举报

leyhzm 发表于 2016-6-30 23:24:50 | 显示全部楼层
我觉得可以是. visit 1point3acres.com for more.
while(node.val !belongsTo(min,man)){
if bigger node=node.left; if smaller node=node.right. From 1point 3acres bbs
}
print(node);//找到对的node再BFS或者DFS来print. 要被打印出来的子树的跟节点肯定属于[min,max]. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 06:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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