合并两棵二叉树

enda 发布于2019-07-25 12:03 / 754人阅读

摘要：合并两棵二叉树思路遇到树问题，首先想到递归将的加到，返回当前处理的结点如果为，把引用指向需要注意处理的问题代码本题以及其它题目代码地址地址

合并两棵二叉树 Merge Two Binary Trees

Given two binary trees and 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 them 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 new tree.

Example 1:

Input: 
    Tree 1                     Tree 2                  
          1                         2                             
         /                        /                             
        3   2                     1   3                        
       /                                                    
      5                             4   7                  
Output: 
Merged tree:
         3
        / 
       4   5
      /     
     5   4   7

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

思路

遇到树问题，首先想到递归

将t2的val加到t1，返回当前处理的t1结点

如果t1为null，把引用指向t2

需要注意处理null的问题

代码

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def mergeTrees(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode
        """
        if t1 is not None and t2 is not None:
            t1.val += t2.val
            t1.left = self.mergeTrees(t1.left, t2.left)
            t1.right = self.mergeTrees(t1.right, t2.right)
        elif t1 is None and t2 is not None:
            t1 = t2
        return t1

本题以及其它leetcode题目代码github地址: github地址

云服务器 GPU云服务器二叉树 python二叉树平衡二叉树实现二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/38650.html

二叉树那些事儿

摘要：大家在聊到二叉树的时候，总会离不开链表。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。存储结构线性表主要由顺序表示或链式表示。链式表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。大家在聊到二叉树的时候，总会离不开链表。这里先带大家一起了解一些基本概念。线性表概念线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关...

Little_XM 2019-08-22 16:28 评论0 收藏0
【数据结构_浙江大学MOOC】第三四五讲树

摘要：然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。输出格式对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出，否则输出。本篇为关于树的编程题，给出编译器 C++(g++)的解答。主要记录题意理解和代码学习过程。 1 树的同构题目给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是同构的。例如图1给出的两棵树就是...

happyfish 2019-07-31 11:12 评论0 收藏0
【LeetCode 二叉树专项】寻找重复的子树（652）

摘要：文章目录题目示例说明限制解法一分析实现复杂度题目给定一棵二叉树的根节点，请返回所有的重复子树。示例示例输入输出示例输入输出示例输入输出说明来源力扣链接限制二叉树中的节点数量在之间。 ...

leejan97 2021-11-15 11:38 评论0 收藏0
tweaked identical binary tree

摘要：原题检查两棵二叉树是否在经过若干次扭转后可以等价。扭转的定义是，交换任意节点的左右子树。等价的定义是，两棵二叉树必须为相同的结构，并且对应位置上的节点的值要相等。样例是扭转后可等价的二叉树。原题检查两棵二叉树是否在经过若干次扭转后可以等价。扭转的定义是，交换任意节点的左右子树。等价的定义是，两棵二叉树必须为相同的结构，并且对应位置上的节点的值要相等。注意：你可以假设二叉树中不会有重复...

frontoldman 2019-08-14 17:07 评论0 收藏0