617. 合并二叉树

淩亂°似流年 2022-12-02 10:50 143阅读 0赞

# 题目： #

[617. 合并二叉树][617.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解：前序遍历 #

## 1. 题解一：递归法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][20200830122850305.gif_pic_center]

## 2. 题解二：迭代法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][20200830123056102.gif_pic_center]

# 代码：前序遍历 #

## 1. 代码一：递归法 ##

import java.util.*;
    
    public class code617 { 
    
        // 解法1: 递归法
        /** * 思想：将一棵树t2，合并到另一棵树t1 * 递归公式：合并当前节点 + 合并左子树 + 合并右子树 * 终止条件：t1或t1的节点为空 * */
        public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) { 
    
            // 1.合并当前节点
            // t1没有，而t2有的节点，直接返回t2
            if(t1 == null)
            { 
                return t2;
            }
    
            // t1有，而t2没有的节点，t1不变，直接返回
            if(t2 == null)
            { 
                return t1;
            }
    
            // 先合并根节点，t1和t2都有的节点，节点值相加，更新t1的值
            t1.val = t1.val + t2.val;
    
            // 2.递归合并左子树和右子树
            t1.left = mergeTrees(t1.left, t2.left);
            t1.right = mergeTrees(t1.right, t2.right);
    
            return t1;
        }
    
        public static void main(String[] args) { 
            Integer nums1[] = {  1, 3, 2, 5 };
            TreeNode root1 = ConstructTree.constructTree(nums1);
            TreeOperation.show(root1);
    
            System.out.println("***************************************");
    
            Integer nums2[] = {  2, 1, 3, null, 4, null, 7 };
            TreeNode root2 = ConstructTree.constructTree(nums2);
            TreeOperation.show(root2);
    
            System.out.println("***************************************");
    
            TreeNode res = mergeTrees(root1, root2);
            TreeOperation.show(res);
        }
    }

## 2. 代码二：迭代法 ##

import java.util.*;
    
    public class code617 { 
    
        // 解法2: 迭代法
        public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) { 
    
            // 如果 t1 和 t2 中，只要有一个是null，函数就直接返回
            if(t1 == null || t2 == null)
            { 
                return t1 == null ? t2: t1;
            }
    
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(t1);
            queue.add(t2);
    
            while(queue.size() > 0)
            { 
                TreeNode r1 = queue.poll();
                TreeNode r2 = queue.poll();
                r1.val = r1.val + r2.val;
    
    			// 如果 r1 和 r2 的左子树都不为空，就放到队列中
    			// 如果 r1 的左子树为空，就把 r2 的左子树挂到 r1 的左子树上
                if(r1.left != null && r2.left != null)
                { 
                    queue.offer(r1.left);
                    queue.offer(r2.left);
                }
                else if(r1.left == null)
                { 
                    r1.left = r2.left;
                }
    
                // 对于右子树也是一样的
                if(r1.right != null && r2.right != null)
                { 
                    queue.offer(r1.right);
                    queue.offer(r2.right);
                }
                else if(r1.right == null)
                { 
                    r1.right = r2.right;
                }
            }
    
            return t1;
        }
    
        public static void main(String[] args) { 
            Integer nums1[] = {  1, 3, 2, 5 };
            TreeNode root1 = ConstructTree.constructTree(nums1);
            TreeOperation.show(root1);
    
            System.out.println("***************************************");
    
            Integer nums2[] = {  2, 1, 3, null, 4, null, 7 };
            TreeNode root2 = ConstructTree.constructTree(nums2);
            TreeOperation.show(root2);
    
            System.out.println("***************************************");
    
            TreeNode res = mergeTrees(root1, root2);
            TreeOperation.show(res);
        }
    }

# 参考： #

1.  [动画演示 递归+迭代 617.合并二叉树][_ 617.]
2.  [合并二叉树][Link 1]

[617.]: https://leetcode-cn.com/problems/merge-two-binary-trees/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/ed3cf4f87d3c4a3caa0f9a139ccb11ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/3e68fbcfef8c4e42a4dcb0e95d557995.png
[20200830122850305.gif_pic_center]: /images/20221123/498c49d743334f37ad74d6b0d402ae87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/8834068c137b4282866b7c82d9f96122.png
[20200830123056102.gif_pic_center]: /images/20221123/11b63f74bc6f47b29dcee2ff05259196.png
[_ 617.]: https://leetcode-cn.com/problems/merge-two-binary-trees/solution/dong-hua-yan-shi-di-gui-die-dai-617he-bing-er-cha-/
[Link 1]: https://leetcode-cn.com/problems/merge-two-binary-trees/solution/he-bing-er-cha-shu-by-leetcode/