合并二叉树

94 合并二叉树

题目描述

给定两个二叉树，你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

输入: 
    Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
         3
        / \
       4   5
      / \   \ 
     5   4   7

解法1 递归法

前序遍历二叉树，再依次把访问到的节点值相加，题目没有说不能改变树的值和结构，我们不用再创建新的节点了，直接将树2合并到树1上再返回树就可以了。

图片来源：https://leetcode-cn.com/problems/merge-two-binary-trees/solution/dong-hua-yan-shi-di-gui-die-dai-617he-bing-er-cha-/

实现代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
       if (t1 == null || t2 == null) {
           return t1 == null ? t2 : t1;
       }
       t1.val += t2.val;
       t1.left = mergeTrees(t1.left, t2.left);
       t1.right = mergeTrees(t1.right, t2.right);
       return t1;
    }
}

复杂度分析

时间复杂度	O(n)
空间复杂度	O(h)，h为树的高度

解法2 迭代法

借助队列来实现广度优先遍历算法，只要两颗树的左节点都不为null，就把将他们放入队列中；同理只要两棵树的右节点都不为null了，也将他们放入队列中。然后我们不断的从队列中取出节点，把他们相加。

图片来源：https://leetcode-cn.com/problems/merge-two-binary-trees/solution/dong-hua-yan-shi-di-gui-die-dai-617he-bing-er-cha-/

代码实现

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
       if (t1 == null || t2 == null) {
           return t1 == null ? t2 : t1;
       }
       LinkedList<TreeNode> queue = new LinkedList<>();
       queue.add(t1);
       queue.add(t2);
       while (queue.size() > 0) {
           TreeNode r1 = queue.remove();
           TreeNode r2 = queue.remove();
           r1.val += r2.val;
           if (r1.left != null && r2.left != null) {
               queue.add(r1.left);
               queue.add(r2.left);
           } else if (r1.left == null) {
               r1.left = r2.left;
           }

           if (r1.right != null && r2.right != null) {
               queue.add(r1.right);
               queue.add(r2.right);
           } else if (r1.right == null) {
               r1.right = r2.right;
           }
       }
       return t1;
    }
}

复杂度分析

时间复杂度	O(n)
空间复杂度	O(n)

在IntelliJ IDEA中测试

package com.cn.algorithm;

import java.util.LinkedList;

/**
 * @Author: cyh
 * @Description: 合并二叉树
 **/
public class MergeTreesDemo {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    TreeNode arrayToTree(Integer[] array, int index) {
        TreeNode root = null;
        if (index < array.length) {
            Integer value = array[index];
            if (value == null) {
                return null;
            }
            root = new TreeNode(value);
            root.left = arrayToTree(array, 2*index + 1);
            root.right = arrayToTree(array, 2*index + 2);
            return root;
        }
        return root;
    }

    /**
     * 递归法
     * @param t1
     * @param t2
     * @return
     */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null || t2 == null) {
            return t1 == null ? t2 : t1;
        }
        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }

    /**
     * 迭代法
     * @param t1
     * @param t2
     * @return
     */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null || t2 == null) {
            return t1 == null ? t2 : t1;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(t1);
        queue.add(t2);
        while (queue.size() > 0) {
            TreeNode r1 = queue.remove();
            TreeNode r2 = queue.remove();
            r1.val += r2.val;
            if (r1.left != null && r2.left != null) {
                queue.add(r1.left);
                queue.add(r2.left);
            } else if (r1.left == null) {
                r1.left = r2.left;
            }

            if (r1.right != null && r2.right != null) {
                queue.add(r1.right);
                queue.add(r2.right);
            } else if (r1.right == null) {
                r1.right = r2.right;
            }
        }
        return t1;
    }

    public static void main(String[] args) {
        MergeTreesDemo demo = new MergeTreesDemo();
        Integer[] arr1 = {1, 3, 2, 5};
        Integer[] arr2 = {2, 1, 3, null, 4, null, 7};
        TreeNode root1 = demo.arrayToTree(arr1, 0);
        TreeNode root2 = demo.arrayToTree(arr2, 0);
        TreeNode root = demo.mergeTrees(root1, root2);
        System.out.println(root); //方便断点调试
    }
}