狗家新鲜fulltime店面，刚面完

刚面试完就来发一下，面试官是白人小哥，刚来狗家两年，一开始不是很热情，心里一凉。但是题目不难，做着做着就熟络起来，一直在交流。最后他说You did a great job, be more confident,和地里大神们比我实力比较弱，但是也积极尝试了。题目的话是一道经典 get nexlargest in BST,确实不太记得了，corner cases想了很多才弄出来，分数设置很低，希望对大家有帮助。

您好！
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

我的代码也在里面，大家加油！求加米！

感谢lz分享，祝早日拿到offer。
下面是我用C#完成的code，好像不必用到parent
        private static TreeNode GetNextBSTNode(TreeNode node)
        {
            if (node == null || node.right == null) return null;
            TreeNode cur = node.right;
            Stack<TreeNode> stk = new Stack<TreeNode>();
            while (stk.Count > 0 || cur != null)
            {
                if (cur != null)
                {
                    stk.Push(cur);
                    cur = cur.left;
                }
                else return stk.Pop();
            }

            return null;
        }

写了一下 请楼主指点

1. public Node getNextLargest(Node node ){
   
2.         if(node.right == null){
   
3.                 node = node.right;
   
4.                 while(node.left !=null){
   
5.                         node = node.left;
   
6.                 }
   
7.                 return node;
   
8.         }
   
9.         while(node.parent != null){
   
10.                 if(node.parent.left == node){
    
11.                                 return node.parent;
    
12.                         }
    
13.                 node = node.parent;
    
14.                         }
    
15.                 }
    
16. }

复制代码

补充内容 (2018-11-28 07:29):
return null

lindali2010 发表于 2018-11-29 07:01
多谢，不过在BST里面若没有node.right 不就是没有比当前node值更大的TreeNode，需要return null吗？

不是。因为比node大的节点并不一定在node右子树中，也可能是node的某个ancestor（只要node在这个ancestor的左子树中）。所以如果node没有右child时，你需要用parent指针不停上溯，直至第一次发现node是在某个ancestor的左子树中为止。如果上溯到root也没有找到这样的ancestor，才能说没有比node更大的值。

排版有点乱，是输出第二大的value就可以了？

请问node的定义是给定的吗? 另外已知node, 找它右孩子的最左孩子不就可以了吗? 为啥还要看 parent

yanl3277881 发表于 2018-11-28 04:29
排版有点乱，是输出第二大的value就可以了？

嗯嗯，输出比当前节点大的第一个value，不好意思。顺序是数据结构->例子->代码。

bc2615 发表于 2018-11-28 05:57
请问node的定义是给定的吗? 另外已知node, 找它右孩子的最左孩子不就可以了吗? 为啥还要看 parent

因为node在不同的位置，情况不一样，可以拿纸写个三层的树，考虑不同的case。

bc2615 发表于 2018-11-28 05:57
请问node的定义是给定的吗? 另外已知node, 找它右孩子的最左孩子不就可以了吗? 为啥还要看 parent

没有右孩子的情况

一只肥青虫 发表于 2018-11-27 18:52
因为node在不同的位置，情况不一样，可以拿纸写个三层的树，考虑不同的case。

明白了!!

dengzeyu147 发表于 2018-11-27 19:28
写了一下 请楼主指点
[mw_shl_code=java,true]public Node getNextLargest(Node node ){
        if(node.right  ...

感觉是对的 学习了

dengzeyu147 发表于 2018-11-28 07:28
写了一下 请楼主指点
[mw_shl_code=java,true]public Node getNextLargest(Node node ){
        if(node.right  ...

第一个if的条件应该是不为空吧