请问cs61a spring2021lab05选择题add_trees有什么好思路？

Question

求思路啊

Answer 1

如果两个树A和B做add_tree操作，得到C，则基本的规则可以解释为：
1.A和B都有的节点，则对应节点上的数值相加，为C的对应节点；
2.A有而B没有的节点，直接复制到C的对应节点上，反之亦然。

思路：
用递归实现，每次合并一层，即当前节点，并在当前层的A、B两棵树都不为空时，逐个合并子节点。
函数形式代码：

def add_tree(A, B):
  if (A is None) and (B is not None):
    return B
  else if (A is not None) and (B is None):
    return A
  # 都不为空, 逐个合并
  val_a, leaves_a = get_val_leaves(A)
  val_b, leaves_b = get_val_leaves(B)
  val_c = val_a + val_b
  leaves_c = merge_leaves(leaves_a, leaves_b)
  if leaves_c is None:
    return val_c
  else:
   return (val_c, leaves_c)

子函数 get_val_leaves，和 merge_leaves，根据语义类推。merge_leaves和add_tree是差不多的逻辑。