近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4649|回复: 24
收起左侧

Facebook 最新电面

[复制链接] |试试Instant~ |关注本帖
chensheng 发表于 2016-5-13 03:04:35 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Failfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x

还是基础不够牢固。
. 鍥磋鎴戜滑@1point 3 acres
题目:
binary tree inorder traversal

class Node {Node left, Node right, Node parent}. From 1point 3acres bbs

Node getNext (Node current) {
} . more info on 1point3acres.com

Fustang 发表于 2016-6-28 00:17:58 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
利用上parent node的一个想法:
if current.right != null, 这种情况最简单,对current.right做in-order traversal找到的第一个就可以了。
if current.right == null, 这时分两种情况:
1. current是其parent的左节点 (current == current.parent.left), 这时current.parent就是要找的. Waral 鍗氬鏈夋洿澶氭枃绔,
2. current是其parent的右节点 (current == current.parent.right),这时向上搜索ancestor, (current = current.parent), 遇到的第一个current是parent左节点就可以停下返回1的情况了
回复 支持 4 反对 1

使用道具 举报

csehao 发表于 2016-5-13 05:50:14 | 显示全部楼层
关注一亩三分地微博:
Warald
        Node getNext(Node current){
. more info on 1point3acres.com
                if(null == current)
                        return null;

                if(null == current.right){
                        while(null != current.parent && current = current.parent.right){
                                current = current.parent;
                        }
                        if(null == current.parent){
                                // it must return from the right most node OR it is the root node, and right child is null.
. 1point 3acres 璁哄潧                                return null;
                        }else{
                                // current = current.parent.left left child.
                                return current.parent;
                        }
                       
                }else{
                        Node c = current.right;.1point3acres缃
                        while(null != c.left){
                                c = c.left;
                        }
                        return c;
                }
        }
回复 支持 3 反对 0

使用道具 举报

blackrose 发表于 2016-5-13 03:39:46 | 显示全部楼层
啥时候投的简历阿
回复 支持 反对

使用道具 举报

 楼主| chensheng 发表于 2016-5-13 03:40:49 | 显示全部楼层
blackrose 发表于 2016-5-13 03:39
啥时候投的简历阿
. visit 1point3acres.com for more.
三月份内推的
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-13 03:42:41 | 显示全部楼层
.鏈枃鍘熷垱鑷1point3acres璁哄潧
再加油面别的!加油加油
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-5-13 03:51:27 | 显示全部楼层
Nose class里为什么要有一个指针指向parent ?
回复 支持 反对

使用道具 举报

csehao 发表于 2016-5-13 04:00:34 | 显示全部楼层
讨论一下 这个题 用recursive call 肯定不能做. 如果题目的意思是给定某个node找下一个. 那么如果左右child都是null的时候. 只能从root开始重新遍历. 如果有一个child不是null. 那么在其child里面找下一个就可以了.
回复 支持 反对

使用道具 举报

edcent 发表于 2016-5-13 04:10:52 | 显示全部楼层
感觉跟bst iterator有点点像.用stack?
回复 支持 反对

使用道具 举报

csehao 发表于 2016-5-13 04:15:58 | 显示全部楼层
如果题目的意思是做一个inorder的tree iterator.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
-google 1point3acres
class Tree{
        Node root;
        Node c;
        Stack<Node> st;
        Tree(){
                // Initializing tree
                st = new Stack<Node>();
                c = self.root;
        }.1point3acres缃
. more info on 1point3acres.com
        Node inOrderGetNext(){
                while(st.isEmpty() && null == c){
                        if(null == c){
                                Node n = st.pop();
                                c = n.right;. more info on 1point3acres.com
                                return n;
                        }else{
                                st.push(c);
                                c = c.left;
                        }
                }
                return null;
        }

}
回复 支持 反对

使用道具 举报

csehao 发表于 2016-5-13 04:30:20 | 显示全部楼层
如果是说给定一个node找下一个 其实感觉不是那么容易写

class Tree{
        Node root;. from: 1point3acres.com/bbs
        Tree(){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                //Initializing. more info on 1point3acres.com
        }
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        Node getNextAux(Node current){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                // get next one including itself.
                if(null == current.left && null == current.right){
                        return current; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                }else{
                        if(null == current.left){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                return getNextAux(current.right);. more info on 1point3acres.com
                        }else{
                                return getNextAux(current.left);
                        }
                }
        }

        Node getNext(Node current){
                if(null == current){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        return null;
                }
                if(null == current.left && null == current.right){
                        Node c = root;
                        Stack<Node> st = new Stack<Node>();

                        while(!st.isEmpty() || null != c){
                                if( null == c){
                                        if(st.isEmpty()){
                                                return null;
                                        }else{
                                                Node n = st.pop();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                                c = n.right;
                                        }
                                }else if( c == current){
                                // we already know c.left c.right is null. from: 1point3acres.com/bbs
                                        if(st.isEmpty()){
                                                return null;
                                        }else{. 1point 3acres 璁哄潧
                                                return st.pop();.1point3acres缃
                                        }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                }       
                        }
                        return null;
                }else{
                        if(null == current.left){-google 1point3acres
                                return getNextAux(current.right);       
                        }else{
                                return getNextAux(current.left);
                        }
                }
        }

}
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-13 04:32:06 | 显示全部楼层
csehao 发表于 2016-5-13 04:30. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
如果是说给定一个node找下一个 其实感觉不是那么容易写 . visit 1point3acres.com for more.

class Tree{

有parent node, 不用那么麻烦。
回复 支持 反对

使用道具 举报

ccrjohn8787 发表于 2016-5-13 04:32:11 | 显示全部楼层
这个解法没用到parent. 感觉给了parent 是不是让用constant space?
回复 支持 反对

使用道具 举报

csehao 发表于 2016-5-13 04:32:24 | 显示全部楼层
写复杂了 其实设置一个boolean记录是否已经reach current Node. true的话就return当前node就可以了.
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-5-13 04:33:59 | 显示全部楼层
https://leetcode.com/problems/inorder-successor-in-bst/

是这道题吗?
回复 支持 反对

使用道具 举报

csehao 发表于 2016-5-13 05:39:51 | 显示全部楼层
blackrose 发表于 2016-5-13 04:32
有parent node, 不用那么麻烦。

果然。。。 有parent node就完全不同了。。。 待我重新写一个...
回复 支持 反对

使用道具 举报

csehao 发表于 2016-5-13 05:41:38 | 显示全部楼层
wtcupup 发表于 2016-5-13 04:33. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
https://leetcode.com/problems/inorder-successor-in-bst/. From 1point 3acres bbs

是这道题吗?
. 1point 3acres 璁哄潧
看不了呢 感觉像是 能帮忙贴一下题目么..
回复 支持 反对

使用道具 举报

ccrjohn8787 发表于 2016-5-13 05:57:40 | 显示全部楼层
www.leetcode.com/problems/binary-search-tree-iterator/
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-5-13 06:07:48 | 显示全部楼层
csehao 发表于 2016-5-13 05:41. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
看不了呢 感觉像是 能帮忙贴一下题目么..

http://buttercola.blogspot.com/2 ... ccessor-in-bst.html
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-5-13 08:16:34 | 显示全部楼层
楼主,所以到底是哪道题啊?
回复 支持 反对

使用道具 举报

 楼主| chensheng 发表于 2016-5-13 23:02:08 | 显示全部楼层
wtcupup 发表于 2016-5-13 08:16.鐣欏璁哄潧-涓浜-涓夊垎鍦
楼主,所以到底是哪道题啊?

都不是一摸一样的,但是类似,我建议leetcode 相关题目都做一下
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-29 17:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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