合并两个二叉树节点和

Question

我正在研究合并两个二叉树的问题(https://www.geeksforgeeks.org/merge-two-binary-trees-node-sum/)我很难理解一些递归。为什么要将递归语句设置为t1。左和t1。对吧？当你这样做的时候，t1。左是否等于两个值？

我只是不确定为什么我们要将递归语句设置为t1.left或t1.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

首先，在构建节点时，可以设置左和右分支-

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)))

在继续之前，让我们在节点上实现\uuuu str\uuu，这样我们就可以可视化树了-

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。由于能够在节点构造函数中指定左和右值，因此编写此函数更容易-

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)))

或者使用操作员模块-

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)))

Answer 2

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

1. 对当前节点进行操作
2. 给一个孩子做手术
3. 给另一个孩子做手术

在这种情况下，对其中一棵树进行合并非常方便。合并当前根节点。然后在左边的子对象上再次出现，它合并了t2。左进入t1。左；您将其分配给t1。左，这样合并后的左子树将干净地替换原始子树。对正确的子树也要这样做。

清楚了吗？