合并两个二叉树节点总和

Question

我正在研究合并两个二叉树节点总和(https://www.geeksforgeeks.org/merge-two-binary-trees-node-sum/(的问题，但我无法理解一些递归。为什么要将递归语句设置为t1.left和t1.right？当你这样做时，t1.left等于两个值吗？

我只是不确定为什么我们将递归语句设置为 t1.leftort1.right'

class newNode: 
def __init__(self, data): 
self.data = data  
self.left = self.right = None

def inorder(node): 
if (not node): 
return
inorder(node.left)  
print(node.data, end = " ")  
inorder(node.right) 

def MergeTrees(t1, t2): 
if (not t1):  
return t2  
if (not t2): 
return t1  
t1.data += t2.data  
t1.left = MergeTrees(t1.left, t2.left)  
t1.right = MergeTrees(t1.right, t2.right)  
return t1 
if __name__ == '__main__': 
# Let us construct the first Binary Tree  
#    1  
#    /   
#    2   3  
# /       
# 4 5    6  
root1 = newNode(1)  
root1.left = newNode(2)  
root1.right = newNode(3)  
root1.left.left = newNode(4)  
root1.left.right = newNode(5)  
root1.right.right = newNode(6)  
# Let us construct the second Binary Tree  
#    4  
#    /   
# 1  7  
# /  /   
# 3  2 6  
root2 = newNode(4)  
root2.left = newNode(1)  
root2.right = newNode(7)  
root2.left.left = newNode(3)  
root2.right.left = newNode(2)  
root2.right.right = newNode(6)  
root3 = MergeTrees(root1, root2)  
print("The Merged Binary Tree is:")  
inorder(root3) 

Answer 1

要使用递归合并树，请遵循典型的公式：

1. 在当前节点上运行
2. 对一个孩子进行手术
3. 对另一个孩子进行手术

在这种情况下，可以就地为其中一棵树完成合并是非常方便的。 合并当前根节点。 然后你在左边的孩子身上重复出现，t2.left合并成t1.left;将此分配给t1.left以便合并的左侧子树完全替换原始子树。 您可以对正确的子树执行相同的操作。

清楚了吗？

Answer 2

首先，在构造Node时可以设置left和right分支 -

class Node:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right

现在不用用node.left = ...和node.right = ...来变异树，我们可以直接构造它们——

# Let us construct the first Binary Tree  
#     1  
#    /   
#   2   3  
#  /      
# 4   5   6  
t1 = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))

在我们继续之前，让我们在Node上实现__str__，以便我们可以可视化树木 -

class Node:
def __init__(...):
# ...
def __str__(self, pre="", child=""):
if self is None:
return "()"
else:
return f"({self.data} {self.left} {self.right})"
print(t1)
# (1 (2 (4 None None) (5 None None)) (3 None (6 None None)))

现在让我们实现merge.能够在Node构造函数中指定left值和right值，可以更轻松地编写此值 -

def merge(t1, t2):
if t1 is None and t2 is None:
return None
elif t1 is None:
return t2
elif t2 is None:
return t1
else:
return Node(t1.data + t2.data, merge(t1.left, t2.left), merge(t1.right, t2.right)
print(merge(t1, t1))
# (2 (4 (8 None None) (10 None None)) (6 None (12 None None)))

现在我们可以看到+如何轻松地进行其他操作。向merge添加另一个参数可以使用任何操作进行合并 -

def merge(f, t1, t2):
if t1 is None and t2 is None:
return None
elif t1 is None:
return t2
elif t2 is None:
return t1
else:
return Node(
f(t1.data, t2.data),
merge(f, t1.left, t2.left),
merge(f, t1.right, t2.right)
)
print(merge(lambda a, b: a + b, t1, t1))
# (2 (4 (8 None None) (10 None None)) (6 None (12 None None)))
print(merge(lambda a, b: a * b, t1, t1))
# (1 (4 (16 None None) (25 None None)) (9 None (36 None None)))

或者使用operator模块 -

from operator import add, mul
print(merge(add, t1, t1))
# (2 (4 (8 None None) (10 None None)) (6 None (12 None None)))
print(merge(mul, t1, t1))
# (1 (4 (16 None None) (25 None None)) (9 None (36 None None)))