合并二叉树

发表于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

LeetCode每日一题，617. Merge Two Binary Trees

先看题目描述

大意就是将两棵二叉树合并，合并规则是若两节点重复，就将其值相加作为新节点，若有一个为空，则以非空的那个为新节点

算法和思路

自己一开始的思路是把 t2 给合并到 t1 上，合并好后将 t1 返回，基本思路就是深度优先遍历两棵二叉树相同位置的各个节点，遍历过程中记录下来父节点，并记录一个标志位表示该节点是父节点的左子节点还是右子节点，若当前 t2 节点为空，则直接返回，因为我们是将 t2 合并到 t1 上；若当前 t1 节点为空，则将当前 t2 节点根据标志位设为父节点的左子节点或右子节点；若均不为空，则将 t2 节点的值加到 t1 节点的值上，然后继续深度优先遍历。

算法源码

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
31
32
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        TreeNode root = new TreeNode(0);
        if (t2 == null) return t1;
        if (t1 == null) return t2;
        dfs(t1, t2, null, 0);
        return t1;
    }

    private void dfs(TreeNode t1, TreeNode t2, TreeNode preNode, int flag) {
        if (t2 == null) {
            return;
        }
        if (t1 == null) {
            if (flag == 0) preNode.left = t2;
            if (flag == 1) preNode.right = t2;
            return;
        }
        t1.val = t1.val  + t2.val;
        dfs(t1.left, t2.left, t1, 0);
        dfs(t1.right, t2.right, t1, 1);
    }
}

后来去看题解，发现题解是创建了棵新的二叉树，作为两棵二叉树的合并，代码更加简洁明了，不过运行效率差不多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode merged = new TreeNode(t1.val + t2.val);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        return merged;
    }
}