BM32. [合并二叉树]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM32. 合并二叉树

同理上面介绍了双树问题，我们从上到下同时前序遍历两个二叉树不就完成了合并成为一个新二叉树，另外这道题目有没有让你想起合并两个排序链表，二叉树可以退化为链表，所以这个题目的特殊情况就是合并链表

合并的规则进行模拟：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替，都为空的节点进行返回

不多说直接进行处理

public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        //如果两个节点都是空的那就返回null
        if(t1 == null && t2 == null)
            return null;
        int value1 = t1 == null? 0 : t1.val;
        int value2 = t2 == null? 0 : t2.val;
        TreeNode cur = new TreeNode(value1 + value2);
        //和链表一样特殊的集中处理按照题意处理即可
        if(t1 == null && t2 != null){
            cur.left = mergeTrees(null, t2.left);
            cur.right = mergeTrees(null, t2.right);
        }
        if(t1 != null && t2 == null){
            cur.left = mergeTrees(t1.left, null);
            cur.right = mergeTrees(t1.right, null);
        }
        if(t1 != null && t2 != null){
            cur.left = mergeTrees(t1.left, t2.left);
            cur.right = mergeTrees(t1.right, t2.right);
        }     
        return cur;
    }

复杂度分析

• 时间复杂度：O(n)，二叉树前序遍历的时间复杂度
• 空间复杂度：O(n)，新建一个二叉树进行返回