题解 | #合并二叉树#

合并二叉树

http://www.nowcoder.com/practice/7298353c24cc42e3bd5f0e0bd3d1d759

①需要额外空间,容易理解

```import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        return rootFirst(t1,t2);
    }
    public TreeNode rootFirst(TreeNode t1, TreeNode t2){
        //有几种情况
        TreeNode root=null;
        //t1左子树空 t2不空| t1左子树不空 t2空 |t1 t2左右子树都空/都不空
        if(t1 == null && t2 == null){
            return null;
        }
        else if(t1 == null &&t2 !=null){
            root = t2;
            return root;
        }
        else if(t1 != null &&t2 == null){
            root = t1;
            return root;
        }
        else if(t1!=null && t2 != null){
            root = new TreeNode(t1.val+t2.val);
            root.left = rootFirst(t1.left,t2.left);
            root.right = rootFirst(t1.right,t2.right);
            return root;
        }
        
        return root;
    }
}
②消除额外空间

``` js
```import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        return rootFirst(t1,t2);
    }
    public TreeNode rootFirst(TreeNode t1, TreeNode t2){
        //有几种情况
        //t1左子树空 t2不空| t1左子树不空 t2空 |t1 t2左右子树都空/都不空
        if(t1 == null && t2 == null){
            return null;
        }
        else if(t1 == null &&t2 !=null){
            return t2;
        }
        else if(t1 != null &&t2 == null){
            return t1;
        }
        else {
            t1.val+=t2.val;
            t1.left = rootFirst(t1.left,t2.left);
            t1.right = rootFirst(t1.right,t2.right);
            return t1;
        }
        
    }
}
全部评论

相关推荐

CARLJOSEPH...:宝宝你戾气太大了
点赞 评论 收藏
分享
06-07 17:17
嘉兴学院 教师
心爱的idea:你孩
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务