合并二叉树

发表于

描述
已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。

例如:
两颗二叉树如下:

  • Tree 1
  • Tree 2
  • 合并后的树

题解
要将一棵二叉树的节点与另一棵二叉树相加合并，肯定需要遍历两棵二叉树，那我们可以考虑同步遍历两棵二叉树，这样就可以将每次遍历到的值相加在一起。遍历的方式有多种，这里推荐前序递归遍历

  • 首先判断t1与t2是否为空，若为则用另一个代替，若都为空，返回的值也是空
  • 然后依据前序遍历的特点，优先访问根节点，将两个根点的值相加创建到新树中
  • 两棵树再依次同步进入左子树和右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package main

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

/**
 * 
 * @param t1 TreeNode类 
 * @param t2 TreeNode类 
 * @return TreeNode类
*/
func mergeTrees( t1 *TreeNode ,  t2 *TreeNode ) *TreeNode {
    // write code here
    if t1 == nil {
        return t2
    }

    if t2 == nil {
        return t1
    }

    t1.Val = t1.Val + t2.Val
    t1.Left = mergeTrees(t1.Left, t2.Left)
    t1.Right = mergeTrees(t1.Right, t2.Right)

    return t1
}