合并二叉树
题目:
两个二叉树要合并为一个,即构造二叉树 !
传入参数为两个root,返回的是一个root !
要从根节点开始合并,自顶向下,即使用前序遍历。
递归三步曲:
- 参数是2个二叉树的根节点,返回值是合并之后新的根节点
- 确定终止条件:
如果root1 ==null 了,两个树合并就应该是 root2 (如果root2也为null即返回 root=null)。
反过来如果root2 == null,那么两个数合并就是root1,
即只要任一方为null,则无需构造新节点root,直接返回不为null的节点 - 单层逻辑即用root1和root2的值构造新root,让递归构造左右子节点
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
// 即构造一个新二叉树
return mer(root1,root2);
}
// 传入2个节点,返回1个新节点
private TreeNode mer(TreeNode root1,TreeNode root2){
// 终止条件
if(root1==null){ // 传2 返1
return root2; // 无需构造新节点
}
if(root2==null){
return root1; // 无需构造新节点
}
// 构造root
TreeNode root=new TreeNode(root1.val+root2.val);
root.left=mer(root1.left,root2.left);
root.right=mer(root1.right,root2.right);
return root;
}
}



