Python3 合并二叉树的实现

题目要求：给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

解决思想：遇到二叉树，首先想到的是递归实现。为了降低空间消耗，两个二叉树合并为一个时，不再新建树。初始给定两个树的当前结点（根结点）t1、t2，若t1和t2节点均不为空，t1节点值更新为t1+t2的值，递归遍历当前节点的左子树和右子树；如果任意其中一个节点为空，且不全为空，返回非空节点；如果两节点均为空，返回None。

直接上代码(￣▽￣)：

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

class Solution:
  def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
    if t1!=None and t2!=None:
      t1.val+=t2.val
      t1.left = self.mergeTrees(t1.left,t2.left)
      t1.right = self.mergeTrees(t1.right,t2.right)
    elif t1==None and t2!=None:
      return t2
    elif t1!=None and t2==None:
      return t1
    else:
      return None
    return t1

时间空间消耗：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • python数据结构之二叉树的遍历实例

    遍历方案   从二叉树的递归定义可知,一棵非空的二叉树由根结点及左.右子树这三个基本部分组成.因此,在任一给定结点上,可以按某种次序执行三个操作:   1).访问结点本身(N)   2).遍历该结点的左子树(L)   3).遍历该结点的右子树(R) 有次序:   NLR.LNR.LRN 遍历的命名 根据访问结点操作发生位置命名:NLR:前序遍历(PreorderTraversal亦称(先序遍历))  --访问结点的操作发生在遍历其左右子树之前.LNR:中序遍历(InorderTraversal)

  • Python中的二叉树查找算法模块使用指南

    python中的二叉树模块内容: BinaryTree:非平衡二叉树  AVLTree:平衡的AVL树  RBTree:平衡的红黑树 以上是用python写的,相面的模块是用c写的,并且可以做为Cython的包. FastBinaryTree  FastAVLTree  FastRBTree 特别需要说明的是:树往往要比python内置的dict类慢一些,但是它中的所有数据都是按照某个关键词进行排序的,故在某些情况下是必须使用的. 安装和使用 安装方法 安装环境: ubuntu12.04, py

  • python实现的二叉树定义与遍历算法实例

    python实现的二叉树定义与遍历算法实例

    本文实例讲述了python实现的二叉树定义与遍历算法.分享给大家供大家参考,具体如下: 初学python,需要实现一个决策树,首先实践一下利用python实现一个二叉树数据结构.建树的时候做了处理,保证建立的二叉树是平衡二叉树. # -*- coding: utf-8 -*- from collections import deque class Node: def __init__(self,val,left=None,right=None): self.val=val self.left=l

  • python数据结构之二叉树的统计与转换实例

    python数据结构之二叉树的统计与转换实例

    一.获取二叉树的深度 就是二叉树最后的层次,如下图: 实现代码: 复制代码 代码如下: def getheight(self):        ''' 获取二叉树深度 '''        return self.__get_tree_height(self.root) def __get_tree_height(self, root):        if root is 0:            return 0        if root.left is 0 and root.righ

  • python实现二叉树的遍历

    本文实例为大家分享了python实现二叉树的遍历具体代码,供大家参考,具体内容如下 代码: # -*- coding: gb2312 -*- class Queue(object): def __init__(self): self.q = [] def enqueue(self, item): self.q.append(item) def dequeue(self): # if self.q != []: if len(self.q)>0: return self.q.pop(0) else

  • python二叉树的实现实例

    树的定义树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样.树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示.树在计算机领域中也得到广泛应用,如在编译源程序时,可用树表示源程序的语法结构.又如在数据库系统中,树型结构也是信息的重要组织形式之一.一切具有层次关系的问题都可用树来描述.树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前驱.树的递归定义如下:(1

  • python数据结构之二叉树的建立实例

    先建立二叉树节点,有一个data数据域,left,right 两个指针域 复制代码 代码如下: # -*- coding: utf - 8 - *- class TreeNode(object): def __init__(self, left=0, right=0, data=0):        self.left = left        self.right = right        self.data = data 复制代码 代码如下: class BTree(object):

  • Python编程实现二叉树及七种遍历方法详解

    Python编程实现二叉树及七种遍历方法详解

    本文实例讲述了Python实现二叉树及遍历方法.分享给大家供大家参考,具体如下: 介绍: 树是数据结构中非常重要的一种,主要的用途是用来提高查找效率,对于要重复查找的情况效果更佳,如二叉排序树.FP-树.另外可以用来提高编码效率,如哈弗曼树. 代码: 用Python实现树的构造和几种遍历算法,虽然不难,不过还是把代码作了一下整理总结.实现功能: ① 树的构造 ② 递归实现先序遍历.中序遍历.后序遍历 ③ 堆栈实现先序遍历.中序遍历.后序遍历 ④ 队列实现层次遍历 #coding=utf-8 cl

  • python数据结构树和二叉树简介

    一.树的定义 树形结构是一类重要的非线性结构.树形结构是结点之间有分支,并具有层次关系的结构.它非常类似于自然界中的树.树的递归定义:树(Tree)是n(n≥0)个结点的有限集T,T为空时称为空树,否则它满足如下两个条件:(1)有且仅有一个特定的称为根(Root)的结点:(2)其余的结点可分为m(m≥0)个互不相交的子集Tl,T2,-,Tm,其中每个子集本身又是一棵树,并称其为根的子树(Subree). 二.二叉树的定义 二叉树是由n(n≥0)个结点组成的有限集合.每个结点最多有两个子树的有序树

  • python二叉树遍历的实现方法

    复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- class TreeNode(object):    def __init__(self,data=0,left=0,right=0):        self.data = data        self.left = left        self.right = right class BTree(object):    def __init__(self,root=0):     

  • Python探索之创建二叉树

    问题 创建一个二叉树 二叉树有限多个节点的集合,这个集合可能是: 空集 由一个根节点,和两棵互不相交的,分别称作左子树和右子树的二叉树组成 创建二叉树,创建节点,再创建节点之间的关系 Python代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:LiYanwei # version:0.1 class TreeNode(object): def __init__ (self, data, left = None, right

随机推荐