题解 | #合并二叉树#
合并二叉树
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;
}
}
}
