Mock 001 Count changes for two N-trees

A change for two N-children tree contains:

1. key is different
2. value is different
3. delete a node
4. add a node

Problem: how many changes to convert tree A to tree B

题目大意：

DD的面经题，多少个改动可以使得existingTree变成newTree

解题思路：

DFS, 比较children，三种情况。若其中一方没有节点，就是计算节点数

解题步骤：

N/A

注意事项：

1. 比较children，三种情况。若其中一方没有节点，就是计算节点数

Python代码：

def 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)