MergeTwoBinaryTrees [source code]

public class MergeTwoBinaryTrees {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t2 == null) return t1;
        if (t1 == null) return t2;
        TreeNode res = new TreeNode(t1.val + t2.val);
        res.left = mergeTrees(t1.left, t2.left);
        res.right = mergeTrees(t1.right, t2.right);
        return res; 
    }
}

这个题真的算是很简单的题目了.

另外, 这个答案已经是最优解.

一般来说, 碰到的 tree 类型的题目, 都是可以用类似 DFS 的思路来搞定, 就跟之前看到find max depth没有头绪一样, 这里这个其实也是一样的.
但是基于 DFS 的 tree 问题其实都特别简单, 直接只要用recursion 的思路, 思考当前 level 干什么就行了.
当你思考当前 level 的时候, 就用类似于 induction 的思路假定底下level 全都是已经 hold 了 ;

这里当前 level 思考的就只有两种情况:
一种是:
1 2
/ \ / \
3 2 1 3
这种情形, 这里的做法就很简单, 直接相加就行了, 属于 overlapping 的情形;

另外一种是:
3 1
/ \ \
5 6 4
的情形, 这种其实你站在当前层的角度来考虑, 其实就是判断一个(5, null, null)和(null)之间怎么合并就行了, 按照题目的意思 ,这两个应该返回(5, null, null), 这个逻辑就很好写了;

Problem Description

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:
Input:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
Output:
Merged tree:
3
/ \
4 5
/ \ \
5 4 7
Note: The merging process must start from the root nodes of both trees.

Hide Tags Tree