合并两个二叉树节点和

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

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

在当前节点上操作
操作一个child
对另一个进行操作child

在这种情况下，可以对其中一棵树进行合并 in-place 非常方便。您合并当前根节点。然后你在左边递归child，它把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)))

现在让我们实施[=23=]。能够在 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)))

合并两个二叉树节点和

Merging two binary trees node sum

algorithm

recursion

binary-tree

data-structures