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
时间空间消耗:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。
相关推荐
-
Python中的二叉树查找算法模块使用指南
python中的二叉树模块内容: BinaryTree:非平衡二叉树 AVLTree:平衡的AVL树 RBTree:平衡的红黑树 以上是用python写的,相面的模块是用c写的,并且可以做为Cython的包. FastBinaryTree FastAVLTree FastRBTree 特别需要说明的是:树往往要比python内置的dict类慢一些,但是它中的所有数据都是按照某个关键词进行排序的,故在某些情况下是必须使用的. 安装和使用 安装方法 安装环境: ubuntu12.04, py
-
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数据结构之二叉树的遍历实例
遍历方案 从二叉树的递归定义可知,一棵非空的二叉树由根结点及左.右子树这三个基本部分组成.因此,在任一给定结点上,可以按某种次序执行三个操作: 1).访问结点本身(N) 2).遍历该结点的左子树(L) 3).遍历该结点的右子树(R) 有次序: NLR.LNR.LRN 遍历的命名 根据访问结点操作发生位置命名:NLR:前序遍历(PreorderTraversal亦称(先序遍历)) --访问结点的操作发生在遍历其左右子树之前.LNR:中序遍历(InorderTraversal)
-
Python编程实现二叉树及七种遍历方法详解
本文实例讲述了Python实现二叉树及遍历方法.分享给大家供大家参考,具体如下: 介绍: 树是数据结构中非常重要的一种,主要的用途是用来提高查找效率,对于要重复查找的情况效果更佳,如二叉排序树.FP-树.另外可以用来提高编码效率,如哈弗曼树. 代码: 用Python实现树的构造和几种遍历算法,虽然不难,不过还是把代码作了一下整理总结.实现功能: ① 树的构造 ② 递归实现先序遍历.中序遍历.后序遍历 ③ 堆栈实现先序遍历.中序遍历.后序遍历 ④ 队列实现层次遍历 #coding=utf-8 cl
-
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实现的二叉树定义与遍历算法实例
本文实例讲述了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二叉树遍历的实现方法
复制代码 代码如下: #!/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数据结构树和二叉树简介
一.树的定义 树形结构是一类重要的非线性结构.树形结构是结点之间有分支,并具有层次关系的结构.它非常类似于自然界中的树.树的递归定义:树(Tree)是n(n≥0)个结点的有限集T,T为空时称为空树,否则它满足如下两个条件:(1)有且仅有一个特定的称为根(Root)的结点:(2)其余的结点可分为m(m≥0)个互不相交的子集Tl,T2,-,Tm,其中每个子集本身又是一棵树,并称其为根的子树(Subree). 二.二叉树的定义 二叉树是由n(n≥0)个结点组成的有限集合.每个结点最多有两个子树的有序树
-
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二叉树的实现实例
树的定义树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样.树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示.树在计算机领域中也得到广泛应用,如在编译源程序时,可用树表示源程序的语法结构.又如在数据库系统中,树型结构也是信息的重要组织形式之一.一切具有层次关系的问题都可用树来描述.树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前驱.树的递归定义如下:(1
-
Python探索之创建二叉树
问题 创建一个二叉树 二叉树有限多个节点的集合,这个集合可能是: 空集 由一个根节点,和两棵互不相交的,分别称作左子树和右子树的二叉树组成 创建二叉树,创建节点,再创建节点之间的关系 Python代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:LiYanwei # version:0.1 class TreeNode(object): def __init__ (self, data, left = None, right
随机推荐
- 详解ASP.NET数据绑定操作中Repeater控件的用法
- JS实现可直接显示网页代码运行效果的HTML代码预览功能实例
- Aspx/Asp.net 防注入程序 V1.0
- CI框架数据库查询缓存优化的方法
- linux环境下python中MySQLdb模块的安装方法
- 通过ASP禁止指定IP和只允许指定IP访问网站的代码
- javascript中eval和with用法实例总结
- JS实现的仿淘宝交易倒计时效果
- 比较详细的WinXP故障恢复控制台完全手册第1/2页
- mysql不重启的情况下修改参数变量
- jQuery获取URL请求参数的方法
- jQuery Attributes(属性)的使用(一、属性篇)
- JavaScript中常见的字符串操作函数及用法汇总
- 微软 Visual Studio 2010官方下载地址给大家
- CI框架安全类Security.php源码分析
- PHP 模拟登陆MSN并获得用户信息
- 小软件锁住系统的USB端口
- 易语言API热键监控实例
- VUE项目中加载已保存的笔记实例方法
- ThinkPHP框架整合微信支付之JSAPI模式图文详解