全新谷歌full time电面

不建树：

1. class SolutionWithoutTreeConstruction:
   
2.     def getLeafMax(self, edges):
   
3.         if not edges: return
   
4.         leaves = set()
   
5.         allNodes = set()
   
6.         parentMap = {}
   
7. 
   
8.         # construct parentMap and leaf set
   
9.         # {10: 5, 15: 5, 5: 8, 6: 8, 7: 6}, set([10, 15, 7])
   
10.         for parent, child in edges:
    
11.             parentMap[child] = parent
    
12.             if parent in leaves:
    
13.                 leaves.remove(parent)
    
14.             if child not in allNodes:
    
15.                 leaves.add(child)
    
16.             allNodes.add(parent)
    
17.             allNodes.add(child)
    
18. 
    
19.         # Search for each leaf in the leaf set
    
20.         for leaf in leaves:
    
21.             curMax = leaf
    
22.             node = leaf
    
23.             while node in parentMap:
    
24.                 node = parentMap[node]
    
25.                 curMax = max(node, curMax)
    
26.             curMax = max(node, curMax)
    
27.             print leaf, curMax

复制代码

建树，然后DFS：

1. class TreeNode:
   
2.     def __init__(self, x):
   
3.         self.val = x
   
4.         self.children = []
   
5. 
   
6. class Tree:
   
7.     def __init__(self):
   
8.         self.root = None
   
9.         self.possibleRoots = set()
   
10.         self.nodes = {}
    
11. 
    
12.     def insertEdge(self, parent, child):
    
13.         if not self.root:
    
14.             parentNode = TreeNode(parent)
    
15.             childNode = TreeNode(child)
    
16.             self.possibleRoots.add(parentNode)
    
17.             parentNode.children.append(childNode)
    
18.             self.nodes[parent] = parentNode
    
19.             self.nodes[child] = childNode
    
20.         else:
    
21.             if parent in self.nodes and child in self.nodes:
    
22.                 self.nodes[parent].children.append(self.nodes[child])
    
23.                 if self.nodes[child] in self.possibleRoots:
    
24.                     self.possibleRoots.remove(self.nodes[child])
    
25.             elif parent in self.nodes and child not in self.nodes:
    
26.                 childNode = TreeNode(child)
    
27.                 self.nodes[child] = childNode
    
28.                 self.nodes[parent].children.append(childNode)
    
29.             elif parent not in self.nodes and child in self.nodes:
    
30.                 parentNode = TreeNode(parent)
    
31.                 self.nodes[parent] = parentNode
    
32.                 self.nodes[parent].children.apped(self.nodes[child])
    
33.                 if self.nodes[child] in self.possibleRoots:
    
34.                     self.possibleRoots.remove(self.nodes[child])
    
35.                 self.possibleRoots.add(self.nodes[parent])
    
36.             else:
    
37.                 parentNode = TreeNode(parent)
    
38.                 childNode = TreeNode(child)
    
39.                 self.possibleRoots.add(parentNode)
    
40.                 parentNode.children.append(childNode)
    
41.                 self.nodes[parent] = parentNode
    
42.                 self.nodes[child] = childNode
    
43.         if len(self.possibleRoots) == 1:
    
44.             self.root = list(self.possibleRoots)[0]
    
45. 
    
46.     def getLeafMax(self):
    
47.         node = self.root
    
48.         self.dfs(node, node.val)
    
49. 
    
50.     def dfs(self, node, curMax):
    
51.         if not node.children:
    
52.             print node.val, curMax
    
53.             return
    
54. 
    
55.         for child in node.children:
    
56.             self.dfs(child, max(curMax, child.val))

复制代码

额，感觉这题是不是可以拿并查集union find来做？