[数据结构与算法]leetcode227合并二叉树

一.题目描述

二.解决办法

1.递归

如果考虑递归，就需要知道递归的终止条件是什么？本题的终止条件是：

• 当root1或者root2为空时，root1为空就返回root2，root2为空就返回root1

if(root1 == null)
    return root2;
if(root2 == null)
    return root1;

• 确定了终止条件后，我的理解是进行一次进行一次合并二叉树的操作。

  class Solution {
      public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
          if(root1 == null)
              return root2;
          if(root2 == null)
              return root1;
          TreeNode root = new TreeNode(root1.val+root2.val);//节点的val值进行合并
          root.left = mergeTrees(root1.left,root2.left);//左子树进行合并
          root.right = mergeTrees(root1.right,root2.right);//右子树进行合并
          return root;
      }
  }

  2.层序遍历

? ? ? ? 使用队列来模拟层序遍历，可以将两棵树的节点放入到队列中。

• 不新建树

class Solution{
    public TreeNode mergeTrees(TreeNode root1,TreeNode root2){
        if(root1 == null)
            return root2;
        if(root2 == null)
            return root1;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root1);
        queue.offer(root2);
        while(!queue.isEmpty()){
            TreeNode node1 = queue.peek();
            queue.poll();
            TreeNode node2 = queue.peek();
            queue.poll();
            node1.val += node2.val;

            if(node1.left != null && node2.left != null){
                queue.offer(node1.left);
                queue.offer(node2.left);   
            }
            if(node1.right != null && node2.right != null){
                queue.offer(node1.right);
                queue.offer(node2.right);   
            }
            if(node1.left == null && node2.left != null){
                node1.left = node2.left;
            }
             if(node1.right == null && node2.right != null){
                node1.right = node2.right;
            }
        }
        return root1;    
    }
}

• 新建树（蛮复杂的）

取三个队列容器，构建一个新的节点，将他输入到queue，通过队列弹出poll每次更新TreeNode,即node,node1,node2.从而左右子树都会更新 。

class Solution{
    public TreeNode mergeTrees(TreeNode root1,TreeNode root2){
        if(root1 == null)
            return root2;
        if(root2 == null)
            return root1;
        TreeNode merged = new TreeNode(root1.val+root2.val);
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue.offer(merged);
        queue1.offer(root1);
        queue2.offer(root2);
        while(!queue1.isEmpty() && !queue2.isEmpty()){
           TreeNode node = queue.poll();
           TreeNode node1 = queue.poll();
           TreeNode node2 = queue.poll();
           TreeNode left1 = node1.left;
           TreeNode left2 = node2.left; 
           TreeNode rigth1 = node1.right;
           TreeNode right2 = node2.right;
           if(left1 != null || left2 != null){
               if(left1 != null && left2 != null){
                   TreeNode left = new TreeNode(left1.val + left2.val);
                   node.left = left;
                   queue.offer(left);
                   queue1.offer(left1);
                   queue2.offer(left2);
               }
               else if(left1 != null){
                   node.left = left1;
               }
               else if(left2 != null){
                   node.left = left2;
               }
           } 
           if(right1 != null || right2 != null){
               if(right1 != null && right2 != null){
                   TreeNode right = new TreeNode(right1.val + right2.val);
                   node.right = right;
                   queue.offer(right);
                   queue1.offer(right1);
                   queue2.offer(right2);
               }
               else if(right1 != null){
                   node.right = right1;
               }
               else if(right2 != null){
                   node.right = right2;
               }
           }
        }
    }
}