Python3 翻转二叉树的实现

提出问题：翻转一棵二叉树。（除根结点以外）

原始二叉树：

新二叉树：

解题思路：遇见二叉树先想到递归。从最下层的叶子结点开始置换左右子节点，一直置换到到最上层的根结点的左右节点为止。

代码如下(￣▽￣)：

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

class Solution:
  def invertTree(self, root: TreeNode) -> TreeNode:
    if root==None:
      return
    left = invertTree(root.left)
    right = invertTree(root.right)
    root.left = right
    root.right = left
    return root

时间与空间消耗：

问题来源：https://leetcode-cn.com/problems/invert-binary-tree/submissions/

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

赞 (0)

相关推荐

  • python二叉树的实现实例

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

  • 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实现的二叉树定义与遍历算法实例

    本文实例讲述了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简单定义与使用二叉树的方法.分享给大家供大家参考,具体如下: class BinaryTree: def __init__(self,rootObj): self.root = rootObj self.leftChild = None self.rightChild = None def insertLeft(self,newNode): if self.leftChild == None: self.leftChild = BinaryTree(newNode) e

  • Python编程求解二叉树中和为某一值的路径代码示例

    题目描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径. 思路:首先要理解题意,是从根节点往子节点连. 1.如果只有根节点或者找到叶子节点,我们就把其对应的val值返回 2.如果不是叶子节点,我们分别对根节点的左子树.右子树进行递归,直到找到叶子结点.然后遍历把叶子结点和父节点对应的val组成的序列返回上一层:如果没找到路径,其实也返回了序列,只不过是[] 代码如下: # -*- coding:utf-

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

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

  • Python实现重建二叉树的三种方法详解

    Python实现重建二叉树的三种方法详解

    本文实例讲述了Python实现重建二叉树的三种方法.分享给大家供大家参考,具体如下: 学习算法中,探寻重建二叉树的方法: 用input 前序遍历顺序输入字符重建 前序遍历顺序字符串递归解析重建 前序遍历顺序字符串堆栈解析重建 如果懒得去看后面的内容,可以直接点击此处本站下载完整实例代码. 思路 学习算法中,python 算法方面的资料相对较少,二叉树解析重建更少,只能摸着石头过河. 通过不同方式遍历二叉树,可以得出不同节点的排序.那么,在已知节点排序的前提下,通过某种遍历方式,可以将排序进行解析

  • Python探索之创建二叉树

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

  • Python3 翻转二叉树的实现

    提出问题:翻转一棵二叉树.(除根结点以外) 原始二叉树: 新二叉树: 解题思路:遇见二叉树先想到递归.从最下层的叶子结点开始置换左右子节点,一直置换到到最上层的根结点的左右节点为止. 代码如下(￣▽￣): # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solutio

  • python3翻转字符串里的单词点的实现方法

    python3翻转字符串里的单词点的实现方法

    给定一个字符串,逐个翻转字符串中的每个单词. 说明: 无空格字符构成一个 单词 . 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括. 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个. 示例 1: 输入:"the sky is blue" 输出:"blue is sky the" 示例 2: 输入:" hello world! " 输出:"world! hello" 解释:输入字符串可以在前

  • python3实现二叉树的遍历与递归算法解析(小结)

    1.二叉树的三种遍历方式 二叉树有三种遍历方式:先序遍历,中序遍历,后续遍历 即:先中后指的是访问根节点的顺序 eg:先序 根左右 中序 左根右 后序 左右根 遍历总体思路:将树分成最小的子树,然后按照顺序输出 1.1 先序遍历 a 先访问根节点 b 访问左节点 c 访问右节点 a(b ( d ( h ) )( e ( i ) ))( c ( f )( g )) -- abdheicfg 1.2 中序遍历 a 先访问左节点 b 访问根节点 c 访问右节点 ( ( ( h ) d ) b ( (

  • Python3 合并二叉树的实现

    题目要求:给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠.你需要将他们合并为一个新的二叉树.合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点. 解决思想:遇到二叉树,首先想到的是递归实现.为了降低空间消耗,两个二叉树合并为一个时,不再新建树.初始给定两个树的当前结点(根结点)t1.t2,若t1和t2节点均不为空,t1节点值更新为t1+t2的值,递归遍历当前节点的左子树和右子树:如果任意其

  • Python3实现二叉树的最大深度

    问题提出: 给定一个二叉树,找出其最大深度.二叉树的深度为根节点到最远叶子节点的最长路径上的节点数. 说明: 叶子节点是指没有子节点的节点. 解决思路:递归法求解.从根结点向下遍历,每遍历到子节点depth+1. 代码实现(￣▽￣): # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Non

  • PHP获取二叉树镜像的方法

    本文实例讲述了PHP获取二叉树镜像的方法.分享给大家供大家参考,具体如下: 问题 操作给定的二叉树,将其变换为源二叉树的镜像. 解决思路 翻转二叉树,有递归和非递归两种方式,非递归就是使用队列. 实现代码 <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ function Mirror(&$

  • 剑指Offer之Java算法习题精讲链表与二叉树专项训练

    剑指Offer之Java算法习题精讲链表与二叉树专项训练

    题目一 链表题——反转链表 根据单链表的头节点head来返回反转后的链表 具体题目如下 解法 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val;

  • python3实现在二叉树中找出和为某一值的所有路径(推荐)

    请写一个程序创建一棵二叉树,并按照一定规则,输出二叉树根节点到叶子节点的路径. 规则如下: 1.从最顶端的根结点,到最下面的叶子节点,计算路径通过的所有节点的和,如果与设置的某一值的相同,那么输出这条路径上的所有节点. 2.从根节点遍历树时,请请按照左到右遍历,即优先访问左子树的节点. 二叉树创建规则:从上到下一层一层的,按照从左到右的顺序进行构造 输入"10,5,12,4,7"值,构造的树如下: 1) 10 2) 10       /     5 3) 10        /\   

  • Python3基础之list列表实例解析

    通常来说Python中任何值都是一个对象,因此任何类型(int.str.list-)都是一个类.而类就必然有它的方法或属性,我们要记下这么多类的所有方法显然是不可能的,对此本文介绍两个小技巧: dir() :内置函数,用来查询一个类或者对象所有属性,比如>>> dir(list). help() :内置函数,用来查询具体的说明文档,比如>>> help(int). 在上一篇的Python3的基本数据类型中,我们初步了解了list列表,也介绍了列表是Python 中使用最

  • Python3学习笔记之列表方法示例详解

    前言 本文主要给大家介绍了关于Python3列表方法的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 1 使用[]或者list()创建列表 user = [] user = list() 2 使用list() 可以将其他类型转换成列表 # 将字符串转成列表 >>> list('abcde') ['a', 'b', 'c', 'd', 'e'] # 将元祖转成列表 >>> list(('a','b','c')) ['a', 'b', 'c']

随机推荐