以copy一棵二叉树为例
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
copy一棵树，根本上说就是copy每一个结点 = copy每个结点对象的val，left和right3个属性，最后返回copy的根节点
对结点val的拷贝很简单，而如何对结点与结点间的left和right关系进行拷贝，从而正确复制树的结构，才是重点
我们要copy每个结点，必然涉及到对结点的访问，那无外乎就是DFS和BFS，分析如下
DFS版copy
定义dfsCopy(root)表示对root为根的树的copy，返回root_copy
则dfsCopy(root) =
- new a TreeNode new_root and copy root.val to new_root.val # 值拷贝
- new_root.left = dfsCopy(root.left) # left拷贝-递归调用
- new_root.right = dfsCopy(root.right) # right拷贝-递归调用
递归出口为root是None的时候
def copyTree(root):
if not root:
return root
new_root = TreeNode(root.val)
new_root.left = copyTree(root.left)
new_root.right = copyTree(root.right)
return new_root
这是一个先序遍历的DFS。可以看到，由于DFS自身的天然优势——DFS算法本身就是沿着结点的left/right执行下去的，当前结点总是直接与其left和right结点相关，拷贝起来很方便
BFS版copy
不同于DFS，BFS逐层向下遍历树。这种层次遍历的形式实际上对于left和right的拷贝不太直观，因为我拷贝某个结点的时候，需要将它和上一层的结点建立left或者righ关系，这就说明我们必须滚动维护两层的结点，这并不是那么方便
实际上，这也不是BFS的问题，因为需要直观获得父子关系的话，往往都是使用DFS。BFS是用来获取兄弟关系的，各有各的擅长场景
要BFS拷贝的话，我们维护两个队列q1 q2。其中q1用来对原树进行层次遍历，q2用来对copy的树进行层次遍历。在BFS中，我们每出队一个结点，就会通过其left和right将下一层的结点入队，因此结点出队的时候就是拷贝其left和right的时候
- 原树结点node入队q1时，进行val拷贝并将拷贝的结点copy_node入队q2
- 原树结点node出队q1时，拷贝node的left和right到copy_node
def copyTree(self, root):
if not root:
return root
q1, q2 = [], []
q1.append(root)
copyroot = TreeNode(root.val)
q2.append(copyroot)
while q1:
l = len(q1)
for i in range(l):
node = q1.pop(0)
copynode = q2.pop(0)
left, right = node.left, node.right
if left:
ll = TreeNode(left.val)
copynode.left = ll
q1.append(left)
q2.append(ll)
if right:
rr = TreeNode(right.val)
copynode.right = rr
q1.append(right)
q2.append(rr)
return copyroot
leetcode 617. 合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树，这里额外要求返回一棵新树，不能用原来的两棵二叉树的任一结点。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
返回新树就是创建或者说拷贝一棵树，这里拷贝的树就是融合之后的那棵树。那么，翻译一下融合条件，获得融合节点后，就转换为了上面基本的树拷贝问题
BFS
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 不修改任何一棵树的结构，返回一棵新树
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if t1 and t2:
q1, q2 = [], []
q1.append(t1)
q2.append(t2)
res_root = TreeNode(t1.val+t2.val)
q = []
q.append(res_root)
while q1 and q2:
l = len(q1)
for i in range(l):
n1, n2, n = q1.pop(0), q2.pop(0), q.pop(0)
# 翻译融合条件，拷贝对应的“融合节点”
# check n1 n2左孩子，都有左孩子，则：
if n1.left and n2.left:
q1.append(n1.left)
q2.append(n2.left)
l_node = TreeNode(n1.left.val+n2.left.val)
n.left = l_node
q.append(l_node)
else:
if n1.left:
l_node = self.copyTree(n1.left)
n.left = l_node
elif n2.left:
l_node = self.copyTree(n2.left)
n.left = l_node
else:
n.left = None
# check n1 n2右孩子，都有右孩子，则：
if n1.right and n2.right:
q1.append(n1.right)
q2.append(n2.right)
r_node = TreeNode(n1.right.val+n2.right.val)
n.right = r_node
q.append(r_node)
else:
if n1.right:
r_node = self.copyTree(n1.right)
n.right = r_node
elif n2.right:
r_node = self.copyTree(n2.right)
n.right = r_node
else:
n.right = None
return res_root
else:
return self.copyTree(t1) if t1 else self.copyTree(t2)
def copyTree(self, root):
if not root:
return root
q1, q2 = [], []
q1.append(root)
copyroot = TreeNode(root.val)
q2.append(copyroot)
while q1:
l = len(q1)
for i in range(l):
node = q1.pop(0)
copynode = q2.pop(0)
left, right = node.left, node.right
if left:
ll = TreeNode(left.val)
copynode.left = ll
q1.append(left)
q2.append(ll)
if right:
rr = TreeNode(right.val)
copynode.right = rr
q1.append(right)
q2.append(rr)
return copyroot
DFS拷贝
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if t1 and t2:
node = TreeNode(t1.val + t2.val)
node.left = self.mergeTrees(t1.left, t2.left)
node.right = self.mergeTrees(t1.right, t2.right)
return node
return self.copyTree(t1) if t1 else self.copyTree(t2)
def copyTree(self, root):
if not root:
return None
node = TreeNode(root.val)
node.left = self.copyTree(root.left)
node.right = self.copyTree(root.right)
return node
嗯，还是DFS简洁可读啊。。。
网友评论