题目地址

617. 合并二叉树

题目概述

Screen Shot 2021-02-12 at 15.03.27

这道题其实就是把二叉树每个节点的值相加，并放到新的二叉树节点，如果某棵树当前节点为空，他的value值是0

其实这个题主要考察的是二叉树遍历，只不过需要同时遍历两棵树，二叉树遍历代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
private Node walk(Node x) {

    if (x == null) {
        return null;
    }

    System.out.println(x.value);
    x.left = walk(x.left);
    x.right = walk(x.right);

    return x;
}

如何实现

  1. 结束条件：当两个数节点都为空，结束当前递归

  2. 每层递归做了什么：计算两个val相加（需要判空），根据该值生成新的节点

  3. 每层递归返回什么：返回上次计算接Node引用

整体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return null;
        }

        int val1 = t1 == null ?  0 : t1.val ;
        int val2 = t2 == null ?  0 :t2.val ;

        int val = val1 + val2;
        TreeNode node = new TreeNode(val);
        node.left = mergeTrees(t1 == null ? null : t1.left, t2 == null ? null : t2.left);
        node.right = mergeTrees(t1 == null? null : t1.right,t2 == null ? null : t2.right);
        return node;

    }
}

不会写递归？如何写递归文章地址：

https://lyl0724.github.io/2020/01/25/1/