狗家MTV面经

回馈社会

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

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

补充内容 (2018-7-28 08:10):
下周要team matching了。不是很清楚HC是已经发生了还是在这之后...

补充内容 (2018-8-3 03:38):
06.25 Sourcer reached out for initial phone conversation
07.02 Talk with Sourcer
07.05 Told Sourcer about my other intervew
07.06 - 07.11 Moved directly to onsite, talked to Recruitor
07.23 - Onsite

补充内容 (2018-8-3 03:39):
07.31 - 08.02 Talked to 5 Teams for Matching
08.03 Request to HC / SVP Review next week

补充内容 (2018-8-11 03:36):
08.09 Invited to lunch with team leaders
08.10 Offer received.

那确实是比我想的难了很多.. 写了蛮久的, 让我想起了红黑树..

点此查看代码..

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

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

楼主这每一题答的都不错 等待楼主喜讯

补充内容 (2018-7-26 09:06):
最后一题应该是刘启柳

贴个自己写的第二轮的代码， 请指正~

1. def leaf_level_traverse(root):
   
2.     cur = root
   
3.     prev = None
   
4.     while cur:
   
5.         if prev == cur.parent: #Traversing down the tree.
   
6.             prev = cur
   
7.             if cur.left:
   
8.                 cur = cur.left
   
9.             else:
   
10.                 print(cur.data)
    
11.                 if cur.right:
    
12.                     cur = cur.right
    
13.                 else:
    
14.                     cur = cur.parent
    
15.         elif prev == cur.left: #Traversing up the tree from the left.
    
16.             cur = cur.right
    
17.             if cur:
    
18.               prev = cur
    
19.               if cur.left:
    
20.                   cur = cur.left
    
21.               else:
    
22.                 print(cur.data)
    
23.                 if cur.right:
    
24.                     cur = cur.right
    
25.                 else:
    
26.                     cur = cur.parent
    
27.         elif prev == cur.right: #Traversing up the tree from the right
    
28.             prev = cur
    
29.             cur = cur.parent
    
30. 
    
31. 
    
32. 
    
33. root = TreeNode(10)
    
34. root.left = TreeNode(8)
    
35. root.right = TreeNode(2)
    
36. root.left.parent = root
    
37. root.right.parent = root
    
38. root.left.left = TreeNode(3)
    
39. root.left.right = TreeNode(5)
    
40. root.left.left.parent = root.left
    
41. root.left.right.parent = root.left
    
42. root.right.left = TreeNode(2)
    
43. root.right.right = TreeNode(7)
    
44. root.right.left.parent = root.right
    
45. root.right.right.parent = root.right
    
46. 
    
47. root.right.right.left = TreeNode(9)
    
48. root.right.right.left.parent = root.right.right
    
49. print("hello")
    
50. 
    
51. 
    
52. """
    
53. Constructed binary tree is
    
54.          10
    
55.         /  \
    
56.        8    2
    
57.       / \ /  \
    
58.       3 5 2   7
    
59.              /
    
60.              9
    
61. """
    
62. 
    
63. leaf_level_traverse(root)

复制代码

请问楼主第二轮节点有parent吗

Jamchaser 发表于 2018-7-25 14:50
请问楼主第二轮节点有parent吗

有的。TreeNode有Left, Right, Value, Parent四个属性，但除此之外就不能再增加或者修改属性了

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

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

这题其实可以在TreeNode里面加一个叫visited的property，然后你也不需要什么pre了，每次要是左右子树都遍历过的话，之前将cur = cur.parent就好了，说白了就是一个树的backtracking。判读是否叶子就看左右子树是否为空就好了，是的话就加入到叶节点和就好了

siren01 发表于 2018-7-25 23:56
这题其实可以在TreeNode里面加一个叫visited的property，然后你也不需要什么pre了，每次要是左右子树都遍历 ...

1.     private class TreeNode
   
2.     {
   
3.         TreeNode left, right;
   
4.         boolean visited;
   
5.         TreeNode parent;
   
6.         int val;
   
7.         
   
8.         public TreeNode(TreeNode parent, int val)
   
9.         {
   
10.             this.val = val;
    
11.             this.parent = parent;
    
12.             left = right = null;
    
13.             visited = false;
    
14.         }
    
15.     }
    
16.    
    
17.     private int printLeafNode(TreeNode root)
    
18.     {
    
19.         int res = 0;
    
20.         TreeNode cur = root;
    
21.         cur.visited = true;
    
22.         while (cur != null)
    
23.         {
    
24.             if (cur.left != null)
    
25.             {
    
26.                 if (cur.left.visited == false)
    
27.                 {
    
28.                     cur = cur.left;
    
29.                     cur.visited = true;
    
30.                 }
    
31.                 else
    
32.                 {
    
33.                     if (cur.right != null)
    
34.                     {
    
35.                         if (cur.right.visited == false)
    
36.                         {
    
37.                             cur = cur.right;
    
38.                             cur.visited = true;
    
39.                         }
    
40.                         else
    
41.                         {
    
42.                             cur = cur.parent;
    
43.                         }
    
44.                     }
    
45.                     else
    
46.                     {
    
47.                         cur = cur.parent;
    
48.                     }
    
49.                 }
    
50.             }
    
51.             else
    
52.             {
    
53.                 if (cur.right != null)
    
54.                 {
    
55.                     if (cur.right.visited == false)
    
56.                     {
    
57.                         cur = cur.right;
    
58.                         cur.visited = true;                        
    
59.                     }
    
60.                     else
    
61.                     {
    
62.                         cur = cur.parent;
    
63.                     }
    
64.                 }
    
65.                 else
    
66.                 {
    
67.                     res += cur.val;
    
68.                     cur = cur.parent;
    
69.                 }               
    
70.             }
    
71.         }
    
72.     }

复制代码

siren01 发表于 2018-7-25 23:56
这题其实可以在TreeNode里面加一个叫visited的property，然后你也不需要什么pre了，每次要是左右子树都遍历 ...

在TreeNode上加本来没有的property就不能算O(1) space啦

dayfine 发表于 2018-7-26 00:28
在TreeNode上加本来没有的property就不能算O(1) space啦

是的是的，就看你和面试官讨论TreeNode是你自己写还是他给你标准的。
标准的就是麻烦一点，就是用pre...别人以贴