leetcode227合并二叉树

一.题目描述

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;
               }
           }
        }
    }
}

上一篇:剑指 Offer 26. 树的子结构


下一篇:Leetcode NO.226 Invert Binary Tree 翻转二叉树