[Leetcode] 617. Merge Two Binary Trees 2つのツリーをマージ
方法1:DFS(divide-and-conquer)
there’s no change on the initial nodes t1 and t2.
方法2:Iterative
using iterative will change t1.
use a list to keep nodes for each level. For current level, if node1 and node2 are both valid, add node2.val to node1.val, if node2 is None, no change, node1 == None will not happen. When go to the next level, only when node1.left exists/node1.right exists, the node will be added into the queue, else node1.left = node2.left/node1.right = node2.right.
time complexity: O(n), space complexity: O(n)
there’s no change on the initial nodes t1 and t2.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if t1 is None and t2 is None:
return None
if t1 is None:
return t2
if t2 is None:
return t1
left = self.mergeTrees(t1.left, t2.left)
right = self.mergeTrees(t1.right, t2.right)
root = TreeNode(t1.val + t2.val)
root.left = left
root.right = right
return root
方法2:Iterative
using iterative will change t1.
use a list to keep nodes for each level. For current level, if node1 and node2 are both valid, add node2.val to node1.val, if node2 is None, no change, node1 == None will not happen. When go to the next level, only when node1.left exists/node1.right exists, the node will be added into the queue, else node1.left = node2.left/node1.right = node2.right.
time complexity: O(n), space complexity: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if t1 is None:
return t2
queue = [[t1, t2]]
while queue:
node1, node2 = queue.pop(0)
if node2 is None:
continue
node1.val += node2.val
if not node1.left:
node1.left = node2.left
else:
queue.append([node1.left, node2.left])
if not node1.right:
node1.right = node2.right
else:
queue.append([node1.right, node2.right])
return t1