首页 > 试题广场 >

合并二叉树

[编程题]合并二叉树
  • 热度指数：59079 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：
两颗二叉树是:
                                                                    Tree 1


                                                                        Tree 2

                                                                    合并后的树为
数据范围：树上节点数量满足 ，树上节点的值一定在32位整型范围内。
进阶：空间复杂度 ，时间复杂度
示例1

输入

{1,3,2,5},{2,1,3,#,4,#,7}

输出

{3,4,5,5,4,#,7}

说明

如题面图
示例2

输入

{1},{}

输出

{1}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Java
小灰灰QAQ头像 小灰灰QAQ 
public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
       public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        f(t1, null, t2, null);
        return t1;
    }

    void f(TreeNode t1Ch, TreeNode parent1, TreeNode t2Ch, TreeNode parent2) {
        if (t1Ch == null && t2Ch == null)
            return;

        if (t1Ch == null) {
           if (parent1.left == t1Ch&&t2Ch==parent2.left)
                parent1.left = t2Ch;
            else {
                parent1.right = t2Ch;
            }
                return;
        }
        if (t2Ch != null) {
            t1Ch.val = t1Ch.val + t2Ch.val;
        }else {
            return;
        }

        f(t1Ch.left, t1Ch, t2Ch.left, t2Ch);
        f(t1Ch.right, t1Ch, t2Ch.right, t2Ch);
    }
}

发表于 2021-12-09 15:29:49 回复(0)
静静等待12头像 静静等待12
前序遍历 

class Solution {
public:
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        // write code here
        if(!t1 && !t2) return nullptr;
        if(!t1) return t2;
        if(!t2) return t1;
        t1->val += t2->val;
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        return t1;
    }
};


发表于 2020-08-06 15:48:43 回复(3)
Java
星辰大海sd头像 星辰大海sd 
public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return null;
        if (t1 == null || t2 == null) return t1 == null ? t2 : t1;
        // 此时 t1、t2 均不为 null
        // 合并节点的值
        t1.val = t1.val + t2.val;
        // 合并左子树
        t1.left = mergeTrees(t1.left, t2.left);
        // 合并右子树
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
}

发表于 2020-11-14 14:49:14 回复(3)
C
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2) {
  if (!t1 || !t2) return t1 ? t1 : t2;
  t1->val += t2->val;
  t1->left  = mergeTrees(t1->left,  t2->left);
  t1->right = mergeTrees(t1->right, t2->right);
  return t1;
}

发表于 2021-07-24 09:22:53 回复(0)
C++
张博_头像 张博_
非递归 
class Solution {
public:
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        // write code here
        if(t1 == nullptr) return t2;
        if(t2 == nullptr) return t1;
        TreeNode* head = t1;
        stack<TreeNode*> st1;
        stack<TreeNode*> st2;
        while(!st1.empty()||t1!=nullptr)
        {
            while(t1!= nullptr&&t2!= nullptr)
            {
                st1.push(t1);
                st2.push(t2);
                t1=t1->left;
                t2=t2->left;
            }
            if(t2 != nullptr )
            {
                t1 = st1.top();
                t1->left =t2;
            }
            t1 = st1.top(); st1.pop();
            t2 = st2.top(); st2.pop();
            t1->val += t2->val;
            if(t1->right==nullptr || t2->right == nullptr)
            {
                if(t1->right == nullptr)
                {
                    t1->right = t2->right;
                }
                t1 = nullptr;
                t2 = nullptr;
            }else
            {
                t1 = t1->right;
                t2 = t2->right;
            }
        }
        return head;
    }
};


发表于 2022-08-14 09:43:34 回复(1)
C++
牛客757388365号头像 牛客757388365号
比较简单的写法 
class Solution {
  public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 && t2) {
            t1->val += t2->val;
            t1->left = mergeTrees(t1->left, t2->left);
            t1->right = mergeTrees(t1->right, t2->right);
            return t1;
        }
        return t1 ? t1 : t2;
    }
};


发表于 2022-06-13 10:36:03 回复(0)
Java
牛客62300892号头像 牛客62300892号
#递归解法，
可以把最后返回的结果用第一个二叉树代替，如果第一棵树为空的话，就让根节点指向右边的对应的二叉树的子节点。
public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) 
    {
        // write code here
        if(t1!=null && t2!=null)
        {
            t1.val=t1.val+t2.val;
           if(mergeTrees ( t1.left,  t2.left)==t2.left)
               t1.left=t2.left;
           if(mergeTrees ( t1.right,  t2.right)==t2.right)
               t1.right=t2.right;   
               
            
            return t1;
        }
        else if(t1==null && t2!=null)
            
            return t2;
        else if (t2==null && t1!=null)
            return t1;
        else
        
           return null; 
    }
}
发表于 2022-05-13 11:51:01 回复(0)
C++
青灯沽酒1头像 青灯沽酒1 
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */

class Solution {
  public:
    /**
     *
     * @param t1 TreeNode类
     * @param t2 TreeNode类
     * @return TreeNode类
     */
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr && t2 == nullptr) return nullptr;
        if (t1 == nullptr && t2 != nullptr) return t2;
        if (t2 == nullptr && t1 != nullptr) return t1;
        t1->val += t2->val;
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        return t1;
    }
};

发表于 2022-04-23 22:34:03 回复(0)
Java
六娃lw头像 六娃lw 
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        if(t1 != null && t2 != null){
            t2.val += t1.val;
            t2.left = mergeTrees(t1.left, t2.left);
            t2.right = mergeTrees(t1.right, t2.right);
        }
        return t2 == null ? t1 : t2;
    }
}
发表于 2020-12-11 23:49:10 回复(0)
C++
Rudrasaum头像 Rudrasaum 
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(!t1) return t2;
        if(!t2) return t1;
        t1->val += t2->val;
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        return t1;
    }
};

发表于 2023-08-28 16:31:13 回复(0)
C
木弎头像 木弎 
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2 ) {
    // write code here
    if(!t1||!t2) return t1?t1:t2;//比较那棵二叉树的子树不为空
    t1->val+=t2->val;//存在的结点的值相加
    t1->left=mergeTrees(t1->left,t2->left);//接收返回更长的左子树
    t1->right=mergeTrees(t1->right,t2->right);//接收返回更长的右子树
    return t1;
}

发表于 2022-11-26 16:43:24 回复(0)
Java
MChen-67头像 MChen-67
递归 dfs 
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null) {
        return t2;
    }
    if (t2 == null) {
        return t1;
    }
    t1.val = t1.val + t2.val;
    t1.left = mergeTrees(t1.left, t2.left);
    t1.right = mergeTrees(t1.right, t2.right);
    return t1;
}


发表于 2022-03-15 09:39:27 回复(0)
Java
The_endless头像 The_endless
递归
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        if(t1==null)
            return t2;
        if(t2==null)
            return t1;
        TreeNode node = new TreeNode(t1.val+t2.val);
        node.left = mergeTrees(t1.left,t2.left);
        node.right = mergeTrees(t1.right,t2.right);
        return node;
    }
发表于 2022-03-12 15:07:55 回复(0)
秋实1头像 秋实1 
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        if (t1==null)return t2;
        if (t2==null)return t1;
        // write code here
        Stack<TreeNode> s1=new Stack<>();
        s1.push(t1);
        Stack<TreeNode> s2=new Stack<>();
        s2.push(t2);
        while (!s1.isEmpty()||!s2.isEmpty()){
            TreeNode pop1 = s1.pop();
            TreeNode pop2 = s2.pop();
            pop1.val+=pop2.val;
            if (pop1.left!=null||pop2.left!=null){
                if (pop1.left==null)pop1.left=new TreeNode(0);
                s1.push(pop1.left);
                if (pop2.left==null)pop2.left=new TreeNode(0);
                s2.push(pop2.left);
            }
            if (pop1.right!=null||pop2.right!=null){
                if (pop1.right==null)pop1.right=new TreeNode(0);
                s1.push(pop1.right);
                if (pop2.right==null)pop2.right=new TreeNode(0);
                s2.push(pop2.right);
            }
        }
        return t1;
    }
}

发表于 2024-09-24 09:38:56 回复(0)
Python2
牛客30511778号头像 牛客30511778号 
#coding:utf-8
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param t1 TreeNode类 
# @param t2 TreeNode类 
# @return TreeNode类
#
class Solution:
    def mergeTrees(self , t1 , t2 ):
        # write code here
        # 若只有一个节点返回另一个，两个都为NULL自然返回NULL
        if not t1: 
            return t2
        if not t2:
            return t1
        # 根左右的方式递归
        root = TreeNode(t1.val + t2.val)
        root.left = self.mergeTrees(t1.left, t2.left)
        root.right = self.mergeTrees(t1.right, t2.right)
        return root

发表于 2024-06-29 11:10:01 回复(0)
Java
sevenkeep头像 sevenkeep 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param t1 TreeNode类
     * @param t2 TreeNode类
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        if (t1 == null) return t2;
        if (t2 == null) return t1;

        t1.val = t1.val + t2.val;

        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);

        return t1;
    }
}

发表于 2024-06-21 17:21:13 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2 ) {
    struct TreeNode *RootTreeNode;
    if(t1==NULL) 
        return t2;
    if(t2==NULL)
        return t1;
    
    RootTreeNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    RootTreeNode->val = t1->val+t2->val;
    RootTreeNode->left = mergeTrees(t1->left, t2->left);
    RootTreeNode->right = mergeTrees(t1->right, t2->right);

    return RootTreeNode;
}

编辑于 2024-03-16 16:59:00 回复(0)
Python3
AntonHan头像 AntonHan 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param t1 TreeNode类 
# @param t2 TreeNode类 
# @return TreeNode类
#
class Solution:
    def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
        # write code here
        if not t1:
            return t2
        if not t2:
            return t1
        head = TreeNode(t1.val + t2.val)
        head.left, head.right = self.mergeTrees(t1.left, t2.left), self.mergeTrees(t1.right, t2.right)
        return head

编辑于 2024-02-12 18:43:56 回复(0)
C
陈让然头像 陈让然
    
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2 ) 
{
    // write code here
    //若t1不存在或都不存在,返回t2
    if(!t1||!t2)
    {
        return t1?t1:t2;
    }
    //相同位置结点值相加
    t1->val+=t2->val;
    //遍历左子树
    t1->left=mergeTrees(t1->left,t2->left);
    //遍历右子树
    t1->right=mergeTrees(t1->right,t2->right);
    //t2移入t1
    return t1;
}


发表于 2023-11-17 17:05:14 回复(0)
C/C++
冬天里的三把火头像 冬天里的三把火
来个非递归版本的解决方案 
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param t1 TreeNode类
     * @param t2 TreeNode类
     * @return TreeNode类
     */
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        // write code here
        if (t1 == NULL) {
            return t2;
        } else if (t2 == NULL) {
            return t1;
        } else {
            TreeNode* ret = NULL;
            vector<pair<TreeNode*, bool>> st1;
            vector<pair<TreeNode*, bool>> st2;
            TreeNode* p1 = t1;
            TreeNode* p2 = t2;
            while (true) {
                if (p1 != NULL) {
                    if (p2 != NULL) {
                        p1->val += p2->val;
                        st1.push_back(make_pair(p1, false));
                        st2.push_back(make_pair(p2, false));
                        p1 = p1->left;
                        p2 = p2->left;
                    } else {
                        if (st2.back().second) {
                            st2.pop_back();
                            p2 = NULL;
                            st1.pop_back();
                            p1 = NULL;
                        } else {
                            st2.back().second = true;
                            p2 = st2.back().first->right;
                            st1.back().second = true;
                            p1 = st1.back().first->right;
                        }
                    }
                } else {
                    if (p2 != NULL) {
                        if (st2.back().second) {
                            st2.back().first->right = NULL;
                            st1.back().second = true;
                            st1.back().first->right = p2;

                        } else {
                            st2.back().first->left = NULL;
                            st1.back().second = false;
                            st1.back().first->left = p2;
                        }
                        p2 = NULL;
                        p1 = NULL;

                    } else {
                        if (st2.back().second) {
                            st2.pop_back();
                            p2 = NULL;
                            st1.pop_back();
                            p1 = NULL;
                        } else {
                            st2.back().second = true;
                            p2 = st2.back().first->right;
                            st1.back().second = true;
                            p1 = st1.back().first->right;
                        }

                    }
                }
                if (st1.empty() && p1 == NULL && st2.empty() && p2 == NULL) {
                    break;
                }
            }
            if (st1.empty() && p1 == NULL && st2.empty() && p2 == NULL) {
                ret = t1;
            }
            return ret;
        }
    }
};

编辑于 2023-10-24 20:25:54 回复(1)
提交观点

问题信息

树
上传者：牛客332641号
难度：
132条回答 5648浏览

热门推荐

通过挑战的用户

查看代码

相关试题

合并二叉树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号