题意

合并两个给定的子二叉树，新的二叉树每个节点是两个二叉树对应节点的和，如果某一个二叉树的节点不存在，则取另外一个二叉树对应节点的值作为新的二叉树对应节点的值。

题目来源：https://leetcode.com/problems/merge-two-binary-trees/

标记难度：Easy

提交次数：1/1

代码效率：98.24%

耗时：25分钟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

分析

主要考察对递归算法的理解。

  • 首先考虑边界，如果两个子二叉树都为空，则新的二叉树必定为空
  • 考虑其中一个子二叉树为空，则新的二叉树直接等于另外一个子二叉树
  • 如果两个子二叉树都不为空，新二叉树节点值为两个子二叉树对应节点的值的和，同时对两个子二叉树的左右子树进行递归调用，仔细想想就明白了

代码

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
/**
 * 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 ret;
        if(t1 == null && t2 == null){
            return null;
        }else if(t1 != null && t2 == null){
            ret = t1;
        }else if(t1 == null && t2 != null){
            ret = t2;
        }else {
            ret = new TreeNode(t1.val + t2.val);
            ret.left = mergeTrees(t1.left,t2.left);
            ret.right = mergeTrees(t1.right,t2.right);
        }
        return ret;
    }
}

当然别人思路的总是最好的 o(╥﹏╥)o

1
2
3
4
5
6
7
8
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null) return t2;
    if (t2 == null) return t1;
    TreeNode result = new TreeNode(t1.val + t2.val);
    result.left = mergeTrees(t1.left, t2.left);
    result.right = mergeTrees(t1.right, t2.right);
    return result;
}

一些废话

学习数据结构的时候，总感觉递归对自己来说是弱项，智商不够用。今天居然一次性直接做出来了。学习数据结构和算法真的能培养思维逻辑和解决问题的能力。fighting !!!