Google 店面面经，求米

littlegrasscao 发表于 2018-12-18 10:24
如果删除的node有左右子树 那删除后形成两个新的树？加上原来的一共三个树？

是的，字数字数字数

1. class TreeNode:
   
2.     def __init__(self,val, left, right):
   
3.         self.val = val
   
4.         self.left = left
   
5.         self.right = right
   
6. 
   
7. 
   
8. badNodes = set()
   
9. def isBadNode(node):
   
10.     if node in badNodes:
    
11.         return True
    
12.     else:
    
13.         return False
    
14. 
    
15. def printTree(root):
    
16.     def getHeight(root):
    
17.         if root is None:
    
18.             return 0
    
19.         return 1 + max(map(getHeight, [root.left, root.right]))
    
20. 
    
21.     def fill(root, i, l ,r):
    
22.         if root is None:
    
23.             return
    
24.         res[i][(l+r)/2] = '' + str(root.val)
    
25.         fill(root.left, i + 1, l, (l + r) / 2)
    
26.         fill(root.right, i + 1, (l + r + 1) / 2, r)
    
27. 
    
28.     height = getHeight(root)
    
29.     res = [[''] * ((1 << height )-1) for _ in range(height)] # need to be (1<< hegith) -1 this () is needed
    
30. 
    
31.     fill(root,0, 0, len(res[0]))
    
32.     for x in res:
    
33.         print x
    
34. 
    
35.     return res
    
36. 
    
37. def printForest(forest):
    
38.     print 'print forest.......'
    
39.     for tree in forest:
    
40.         printTree(tree)
    
41.         print '========'
    
42. 
    
43. def trimTree(root):
    
44.     forest = []
    
45.     def helper(node, parent_added):
    
46.         if node is None:
    
47.             return None
    
48. 
    
49.         if isBadNode(node):
    
50.             helper(node.left, False)
    
51.             helper(node.right, False)
    
52.         else:
    
53.             if not parent_added:
    
54.                 forest.append(node)
    
55.             helper(node.left, True)
    
56.             helper(node.right, True)
    
57. 
    
58.         # unlink
    
59.         if isBadNode(node.left):
    
60.             node.left = None
    
61.         if isBadNode(node.right):
    
62.             node.right = None
    
63. 
    
64.     helper(root, False)
    
65.     return forest
    
66. 
    
67. 
    
68. 
    
69. 
    
70. node10 = TreeNode(10, None, None)
    
71. node8  = TreeNode(8, None, None)
    
72. node4 = TreeNode(4, None, None)
    
73. node2 = TreeNode(2, None, None)
    
74. node9 = TreeNode(9, None, None)
    
75. node13 = TreeNode(13, None, None)
    
76. node11 = TreeNode(11, None, None)
    
77. node12 = TreeNode(12, None, None)
    
78. 
    
79. node10.left = node8
    
80. node8.right = node9
    
81. node8.left = node4
    
82. node4.left = node2
    
83. 
    
84. node10.right = node13
    
85. node13.left = node11
    
86. 
    
87. node11.right = node12
    
88. 
    
89. printTree(node10)
    
90. 
    
91. 
    
92. #badNodes = set([node10, node8, node12])
    
93. #badNodes = set([node10])
    
94. badNodes = set([node8])
    
95. 
    
96. forest = trimTree(node10)
    
97. 
    
98. printForest(forest)
    
99. 
    
100. 
     
101. 
     
102. def constructBST(badNodes, forest):
     
103.     nodes = list(badNodes) + forest
     
104.     nodes = sorted(nodes, key = lambda x: x.val)
     
105. 
     
106.     print 'nodes in hand are', [n.val for n in nodes]
     
107. 
     
108.     def dfs(nums, i, j):
     
109.         if i > j:
     
110.             return None
     
111.         mid = (j - i) /2 + i
     
112.         root = nums[mid]
     
113.         left = dfs(nums, i, mid -1)
     
114.         if left:
     
115.             root.left = left
     
116.         
     
117.         right = dfs(nums, mid +1, j)
     
118.         if right:
     
119.             root.right = right
     
120.         return root
     
121. 
     
122.     root = dfs(nodes,0, len(nodes)-1)
     
123.     printTree(root)
     
124.     return root
     
125. 
     
126. 
     
127. constructBST(badNodes, forest)

复制代码

楼主。第一问这个删除的nodes 会是多个？还是一定只会删去一个啊？

然后就是第二问BST的话怎么能给node, 和forest能返回原来的树呢？不是可能会有很多BST满足input条件的么

salamanderrex1 发表于 2018-12-28 20:01
楼主。第一问这个删除的nodes 会是多个？还是一定只会删去一个啊？

然后就是第二问BST的话怎么能给node, ...

删除的话可能是多个，构建BST的话应该不需要一模一样，合理的就好

ZihaoZhai 发表于 2018-12-29 01:26
删除的话可能是多个，构建BST的话应该不需要一模一样，合理的就好

啊。懂了，谢谢楼主。