亚麻aws电面跪经

今天下午刚刚面完的aws电话面试, 老中出题, BST中给定特定节点求中序遍历的前一个节点predecessor.  注意没有给root节点,  扯了半天,  弄了半天发现要还是要设置parent指针, 没做过啊,  leetcode也没有考过这道题,  第一反应找到root节点再用常规方法找给定节点的前一个,  面试官说不用找root,  立马感觉这次要凉了, 没做过这道题的话, 想当场做出来得要对bst的各种属性奇技淫巧非常熟悉才行. 下面是我电面结束后写

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

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

      temp = cur;
              cur = cur.parent;
          }
          return cur == null ? -1 : cur.val;
      } else return -1;
  }


求大米安慰.

没有parent指针这题无解

楼主只做了一道题么？A家phone interview需要做几道题呢？
老中和你谈项目了么？
周五也是 AWS phone interview，也是老中interviewer，求保佑！

楼主，
这段代码什么意思啊？
else if (node.parent != null) {. 鍥磋?鎴戜滑@1point 3 acres
          Node cur = node;. 鐗涗汉浜戦泦,涓

乱码了 不好意思。

楼主，
这段代码什么意思啊？

1. else if (node.parent != null) {
   
2.           Node cur = node;
   
3.           Node temp = null;
   
4.           while (cur != null && cur.left == temp) {
   
5.               temp = cur;
   
6.               cur = cur.parent;
   
7.           }
   
8.           return cur == null ? -1 : cur.val;
   
9.       }else if (node.parent != null) {
   
10.           Node cur = node;
    
11.           Node temp = null;
    
12.           while (cur != null && cur.left == temp) {
    
13.               temp = cur;
    
14.               cur = cur.parent;
    
15.           }
    
16.           return cur == null ? -1 : cur.val;
    
17.       }

复制代码

第一个if我看懂了，就是求左子树中最大的店。 第二个if也就是上面的code，我没看懂。 难道不是应该求当前node的parent的右节点是否为当前node吗？

hyliu0000 发表于 2018-2-9 06:37
乱码了 不好意思。

楼主，

     A
        B
      C
   node

是这种情况，node的predecessor是A。这个代码就是为了找到这个predecessor。

左子树非空就找左子树最大的，左子树为空就一直找parent一直找到一个比当前值小的。

哪里的职位 最近的职位都是online两道题的？

https://segmentfault.com/a/1190000005797856
应该类似这个题

如果左子树为空 貌似不用像楼主那样写？
直接沿着他爹一直找到比他小那一个节点就可以了？
如楼上上上所说“左子树非空就找左子树最大的，左子树为空就一直找parent一直找到一个比当前值小的。"