A change for two N-children tree contains:
- key is different
- value is different
- delete a node
- add a node
Problem: how many changes to convert tree A to tree B
题目大意：
DD的面经题，多少个改动可以使得existingTree变成newTree
解题思路：
DFS, 比较children，三种情况。若其中一方没有节点，就是计算节点数
解题步骤：
N/A
注意事项：
- 比较children，三种情况。若其中一方没有节点，就是计算节点数
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29def changeNodes(self, existingTree, newTree) -> int:
if not existingTree and not newTree:
return 0
if not existingTree or not newTree:
return self.count(existingTree) + self.count(newTree)
res = 0 if existingTree.key == newTree.key and existingTree.val == newTree.val else 1
existing_children_dict = self.get_children_dict(existingTree.children)
new_tree_children_dict = self.get_children_dict(newTree.children)
for key in existing_children_dict.keys() & new_tree_children_dict.keys(): # in both
res += self.changeNodes(existing_children_dict[key], new_tree_children_dict[key])
for key in existing_children_dict.keys() - new_tree_children_dict.keys(): # in existing tree not in new tree
res += self.count(existing_children_dict[key])
for key in new_tree_children_dict.keys() - existing_children_dict.keys(): # in new tree not in existing tree
res += self.count(new_tree_children_dict[key])
return res
def count(self, root):
if not root:
return 0
res = 0
for child in root.children:
res += self.count(child)
return 1 + res
def get_children_dict(self, children):
key_to_node = {}
for child in children:
key_to_node[child.key] = child
return key_to_node
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
