今年面得差不多了，热乎乎的palantir面筋送给大家

面之前就觉着会比较难了。
有个tree，tree里面node的结构包含一个char和左右指针。同一个node的左右指针可以指向同一个child节点，不同node也可以指向相同chil

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

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

k个节点的存的char。考察点在于由于中序遍历时会有重复节点，如何才能节省时间找到第k个。楼主比较挫，不会做，大家可以讨论哈~

如果有一个队伍 1， 2， 。。。 k， k+1， 。。。。 n， 第二次遇到某节点，就不再把它加入队伍中？

简单想的话就把每个节点涂上色，分别代表已遍历全部子树，已开始遍历子树，和从未遇到过这个节点，recurse的时候如果遇到见过的节点，就不recurse它了。。。Intro to Algorithms 有的。。

如果有一个队伍 1， 2， 。。。 k， k+1， 。。。。 n， 第二次遇到某节点，就不再把它加入队伍中？

简单想的话就把每个节点涂上色，分别代表已遍历全部子树，已开始遍历子树，和从未遇到过这个节点，recurse的时候如果遇到见过的节点，就不recurse它了。。。Intro to Algorithms 有的。。

如果有一个队伍 1， 2， 。。。 k， k+1， 。。。。 n， 第二次遇到某节点，就不再把它加入队伍中？

简单想的话就把每个节点涂上色，分别代表已遍历全部子树，已开始遍历子树，和从未遇到过这个节点，recurse的时候如果遇到见过的节点，就不recurse它了。。。Intro to Algorithms 有的。。

加size域， 二分。 O(log n)

北美农民 发表于 2014-12-19 05:57
加size域， 二分。 O(log n)

能说具体一点吗？O(logn)是总的time complexity?

北美农民 发表于 2014-12-19 05:57
加size域， 二分。 O(log n)

size域值得什么？

北美农民 发表于 2014-12-19 05:57
加size域， 二分。 O(log n)

你好，求教size域的具体解法。。

顺便贴上我的解法。。求各位大牛指正！

1. public TreeNode getNodeK(TreeNode root, int k){
   
2.                 if (root == null || k <= 0){
   
3.                         return null;
   
4.                 }
   
5.                 Stack<TreeNode> s = new Stack<TreeNode>();
   
6.                 Set<TreeNode> visited = new HashSet<TreeNode>();
   
7.                 TreeNode rst = null;
   
8.                 TreeNode p = root;
   
9.                 int counter = 0;
   
10.                
    
11.                 while (s.size() > 0 || p != null){
    
12.                         if (p != null && !visited.contains(p)){
    
13.                                 s.push(p);
    
14.                                 p = p.left;
    
15.                         }
    
16.                         else{
    
17.                                 p = s.pop();
    
18.                                 visited.add(p);
    
19.                                 counter++;
    
20.                                 if (counter == k){
    
21.                                         rst = p;
    
22.                                         break;
    
23.                                 }
    
24.                                 p = visited.contains(p.right) ? null : p.right;
    
25.                         }
    
26.                 }
    
27.                 return rst;
    
28.         }

复制代码