LeetCode（Tree)617. Merge Two Binary Trees

短命女 2023-09-26 20:37 89阅读 0赞

# 1.问题 #

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

Example 1:  
![在这里插入图片描述][1426e1ce61a7420288ebfd941c3ec2b3.png]

> Input: root1 = \[1,3,2,5\], root2 = \[2,1,3,null,4,null,7\]  
> Output: \[3,4,5,5,4,null,7\]

Example 2:

> Input: root1 = \[1\], root2 = \[1,2\]  
> Output: \[2,2\]

Constraints:

*  The number of nodes in both trees is in the range \[0, 2000\].
 *  \-104 <= Node.val <= 104

# 2. 解题思路 #

## 方法1： ##

深度优先搜索

> 使用深度优先搜索（DFS）来实现合并两个二叉树。使用一个栈来存储待合并的节点，每次从栈中取出一个节点进行合并，将对应的左右子树节点放入栈中，直到栈为空为止。
> 
> 1.  若其中一个树为空，则直接返回另一个树
> 2.  否则，将两个根节点的值相加，创建一个新的节点，并递归合并两个左子树和右子树
> 3.  最终返回合并后的树。

## 方法2： ##

广度优先搜索：

>  *  通过创建队列，逐层遍历两棵树，合并每个节点的左子节点和右子节点。
>  *  在遍历时，将每个节点的左子节点和右子节点分别入队，直到两个队列均为空。
>  *  最终返回合并后的根节点。  
>     1.创建一个队列，并将两棵二叉树的根节点入队。  
>     2.迭代遍历队列，每次从队列中取出一个节点，并将它们的值相加，创建一个新的节点作为合并后的节点，将该节点作为新二叉树的子节点。  
>     3.如果两棵二叉树的左子树都非空，将它们的左子节点入队。  
>     4.如果两棵二叉树的右子树都非空，将它们的右子节点入队。  
>     5.当队列为空时，遍历结束，返回新的二叉树的根节点。

## 方法3： ##

迭代方法:

>  *  可以使用迭代来实现合并两个二叉树。
>  *  将两个根节点分别放入一个栈中，然后每次取出栈顶节点进行合并，将对应的左右子树节点放入栈中
>  *  直到栈为空为止。

# 3. 代码 #

## 代码1： ##

* Definition for a binary tree node.
     * public class TreeNode {
        
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {
        }
     *     TreeNode(int val) {
         this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
        
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    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);
    		// 递归合并两个左子树
    		root.left = mergeTrees(root1.left, root2.left);
    		// 递归合并两个右子树
    		root.right = mergeTrees(root1.right, root2.right);
    		// 返回合并后的树
    		return root;
        }
    }

> 解题思路基本相同，没有新建TreeNode，而是在原来root1基础上合并

class Solution {
        
     public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        
            if (t1 == null) return t2;
            if (t2 == null) return t1;
            t1.val += t2.val;
            t1.left = mergeTrees(t1.left, t2.left);
            t1.right = mergeTrees(t1.right, t2.right);
            return t1;
        }
    }

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);
            merged.left = mergeTrees(root1.left, root2.left);
            merged.right = mergeTrees(root1.right, root2.right);
            return merged;
        }
    }

## 代码2： ##

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);
    
            // 创建队列
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
            Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
    
            // 将两棵树的根节点入队
            queue.add(root);
            queue1.add(root1);
            queue2.add(root2);
    
            while(!queue1.isEmpty() && !queue2.isEmpty()){
        
                TreeNode node = queue.poll(), node1 = queue1.poll(), node2 = queue2.poll();
                // 合并节点的左子节点
                if(node1.left!=null || node2.left!=null){
        
                    if(node1.left!=null && node2.left!=null){
        
                        TreeNode left = new TreeNode(node1.left.val+node2.left.val);
                        node.left = left;
                        queue.add(left);
                        queue1.add(node1.left);
                        queue2.add(node2.left);
                    } else if(node1.left!=null){
        
                        node.left = node1.left;
                    } else if(node2.left!=null){
        
                        node.left = node2.left;
                    }
                }
                // 合并节点的右子节点
                if(node1.right!=null || node2.right!=null){
        
                    if(node1.right!=null && node2.right!=null){
        
                        TreeNode right = new TreeNode(node1.right.val+node2.right.val);
                        node.right = right;
                        queue.add(right);
                        queue1.add(node1.right);
                        queue2.add(node2.right);
                    } else if(node1.right!=null){
        
                        node.right = node1.right;
                    } else if(node2.right!=null){
        
                        node.right = node2.right;
                    }
                }
            }
            return root;
        }
    }

## 代码3： ##

class Solution {
        
        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        
            // 如果root1为空，则返回root2
            if (root1 == null) {
        
                return root2;
            }
            // 如果root2为空，则返回root1
            if (root2 == null) {
        
                return root1;
            }
    
            // 使用栈来进行迭代操作，初始时把root1和root2打包为一个节点对入栈
            Stack<TreeNode[]> stack = new Stack<>();
            stack.push(new TreeNode[]{
        root1, root2});
    
            // 当栈不为空时，一直循环
            while (!stack.isEmpty()) {
        
                // 弹出一个节点对
                TreeNode[] nodes = stack.pop();
                // 如果左右子树中有一个为空，则跳过此次循环
                if (nodes[0] == null || nodes[1] == null) {
        
                    continue;
                }
                // 把root2的值加到root1上
                nodes[0].val += nodes[1].val;
                // 如果root1的左子树为空，就把root2的左子树接到root1上
                if (nodes[0].left == null) {
        
                    nodes[0].left = nodes[1].left;
                } else {
        
                    // 如果root1的左子树不为空，则把root1的左子树和root2的左子树打包为一个节点对入栈
                    stack.push(new TreeNode[]{
        nodes[0].left, nodes[1].left});
                }
                // 如果root1的右子树为空，就把root2的右子树接到root1上
                if (nodes[0].right == null) {
        
                    nodes[0].right = nodes[1].right;
                } else {
        
                    // 如果root1的右子树不为空，则把root1的右子树和root2的右子树打包为一个节点对入栈
                    stack.push(new TreeNode[]{
        nodes[0].right, nodes[1].right});
                }
            }
    
            // 返回合并后的root1
            return root1;
        }
    }

[1426e1ce61a7420288ebfd941c3ec2b3.png]: https://img-blog.csdnimg.cn/1426e1ce61a7420288ebfd941c3ec2b3.png

发表评论取消回复

表情：

评论列表（有 0 条评论，89人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode（Tree)617. Merge Two Binary Trees

1.问题 You are given two binary trees root1 and root2. Imagine that when you put one o

短命女/ 2023年09月26日 20:37/ 0 赞/ 90 阅读

相关 LeetCode - Easy - 617. Merge Two Binary Trees

Topic Tree Description [https://leetcode.com/problems/merge-two-binary-trees/]

忘是亡心i/ 2023年01月08日 08:03/ 0 赞/ 91 阅读

相关 leetcode 617. Merge Two Binary Trees | 617. 合并二叉树（Java）

题目 [https://leetcode-cn.com/problems/merge-two-binary-trees/][https_leetcode-cn.com_p

￡神魔★判官ぃ/ 2022年10月17日 13:49/ 0 赞/ 110 阅读

相关 [Leetcode]617. Merge Two Binary Trees

Iteration solution In order to merge the 2 binary trees, we need to traverse them in

不念不忘少年蓝@/ 2022年06月14日 10:48/ 0 赞/ 129 阅读

相关 [leetcode]: 617. Merge Two Binary Trees

1.题目 Given two binary trees and imagine that when you put one of them to cover the ot

超、凢脫俗/ 2022年06月14日 09:19/ 0 赞/ 125 阅读

相关【leetcode】617. Merge Two Binary Trees

一、题目描述 Given two binary trees and imagine that when you put one of them to cover the ot

红太狼/ 2022年06月10日 08:53/ 0 赞/ 169 阅读

相关 Merge Two Binary Trees

[原题链接][Link 1] 题目主要的意思如下： 1. 如果两棵树内对应节点均有数据，则节点值相加； 2. 如果没有，则将对应子树进行拼接。思路：分治法。因

╰半橙微兮°/ 2022年06月04日 00:42/ 0 赞/ 80 阅读

相关 [leetcode] 617. Merge Two Binary Trees

> 题目描述给定两棵树，要求合并它们，如果节点重合则新合并的树的节点为它们之和，否则不变。 > 思路简单递归，c语言怎么创建新节点忘记了，就直接写的。 > 代码

太过爱你忘了你带给我的痛/ 2022年05月30日 09:48/ 0 赞/ 145 阅读

相关 617. Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, som

朱雀/ 2022年04月22日 20:06/ 0 赞/ 126 阅读

相关刷题leetcode--617. Merge Two Binary Trees

617. Merge Two Binary Trees Given two binary trees and imagine that when you put one

港控/mmm°/ 2021年10月09日 03:48/ 0 赞/ 207 阅读