algorithm - 合并两个二叉树节点和

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. 对一个 child 进行手术
3. 给另一个 child 做手术

在这种情况下，对其中一棵树就地进行合并非常方便。您合并当前根节点。然后你在左 child 上重复，它将 t2.left 合并到 t1.left 中；您将其分配给 t1.left，以便合并后的左子树干净地替换原始树。您对右子树执行相同的操作。

还清楚吗？