leetCode167|合并二叉树

码农王同学

发布于 2021-01-15 11:04:11

2850

发布于 2021-01-15 11:04:11

文章被收录于专栏：后端Coder

一，合并二叉树

1，问题简述

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

2，示例描述

示例 1:

输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7
注意: 合并必须从两个树的根节点开始。

3，题解思路

利用递归的思想进行解决

4，题解程序

public  class MergeTreesTest2 {
    public static void main(String[] args) {
        TreeNode t1=new TreeNode(1);
        TreeNode t12=new TreeNode(3);
        TreeNode t13=new TreeNode(2);
        TreeNode t14=new TreeNode(5);
        t1.left=t12;
        t1.right=t13;
        t12.left=t14;

        TreeNode t2=new TreeNode(2);
        TreeNode t22=new TreeNode(1);
        TreeNode t23=new TreeNode(3);
        TreeNode t24=new TreeNode(4);
        TreeNode t25=new TreeNode(7);
        t2.left=t22;
        t2.right=t23;
        t22.right=t24;
        t23.right=t25;
        TreeNode treeNode = mergeTrees(t1, t2);
        System.out.println("treeNode = " + treeNode);


    }

    public static  TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return null;
        }
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode root = new TreeNode(t1.val + t2.val);
        root.left = mergeTrees(t1.left, t2.left);
        root.right = mergeTrees(t1.right, t2.right);
        return root;
    }
}