有段时间没有写代码了，脑子都生锈了，今后争取笔耕不辍（立flag，以后打脸）
随机一道Leecode题， Merge Two Binary Trees，题目基本描述如下：
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
题目是很简单的题目，但是由于大脑生锈，竟然也折腾了半天。
解题思路是使用迭代。
令tree1为t1，tree2为t2
merge tree的root肯定为t1.root+t2.root
对于merge tree的left，可以认为是以t1.left为root的tree与以t2.left为root的tree合并的结果
同样类似，对于merge tree的right，可以认为是t1.right为root的tree与以t2.right为root的tree合并的结果
如此反复，通过迭代就很容易得到结果了。
做个备忘，在python3中，使用TreeNode来构建树，树当前的节点的值为val，节点的左子节点为left，节点的右子为right.
代码如下：
class Solution:
def mergeTrees(self, t1, t2):
"""
:type t1: TreeNode
:type t2: TreeNode
:rtype: TreeNode
"""
if (t1 is None) and (t2 is None):
return
if (t1 is None):
return t2
if (t2 is None):
return t1
t1.val += t2.val
t1.left = self.mergeTrees(t1.left,t2.left)
t1.left = self.mergeTrees(t1.right,t2.right)
return t1
def stringToTreeNode(input):
input = input.strip()
input = input[1:-1]
if not input:
return None
inputValues = [s.strip() for s in input.split(',')]
root = TreeNode(int(inputValues[0]))
nodeQueue = [root]
front = 0
index = 1
while index < len(inputValues):
node = nodeQueue[front]
front = front + 1
item = inputValues[index]
index = index + 1
if item != "null":
leftNumber = int(item)
node.left = TreeNode(leftNumber)
nodeQueue.append(node.left)
if index >= len(inputValues):
break
item = inputValues[index]
index = index + 1
if item != "null":
rightNumber = int(item)
node.right = TreeNode(rightNumber)
nodeQueue.append(node.right)
return root
def treeNodeToString(root):
if not root:
return "[]"
output = ""
queue = [root]
current = 0
while current != len(queue):
node = queue[current]
current = current + 1
if not node:
output += "null, "
continue
output += str(node.val) + ", "
queue.append(node.left)
queue.append(node.right)
return "[" + output[:-2] + "]"
def main():
import sys
def readlines():
for line in sys.stdin:
yield line.strip('
')
lines = readlines()
while True:
try:
line = next(lines)
t1 = stringToTreeNode(line);
line = next(lines)
t2 = stringToTreeNode(line);
ret = Solution().mergeTrees(t1, t2)
out = treeNodeToString(ret);
print(out)
except StopIteration:
break
if __name__ == '__main__':
main()