LeetCode 344 Merge Two Binary Trees

一份执着✘

修改于 2019-12-30 16:57:18

4020

题意

合并两颗二叉树, 合并规则是相同位置的值进行相加, 返回生成后二叉树的根节点.

例 :

输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

解法

基本思路是将两棵树, 合并到左树上, 基本规则是只有当 tree1 和 tree2 相同位置的节点都不为空时, 才能进行相加操作, 当 tree1 为空时, 把 tree2 的节点嫁接过来, 当 tree2 为空时, 保留 tree1 即可. 以此类推, 把每个节点都看成根节点即可.

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        } else if (t2 == null) {
            return t1;
        }

        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Two Binary Trees. Memory Usage: 41.2 MB, less than 78.32% of Java online submissions for Merge Two Binary Trees.

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-04-09，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树