[Leetcode][python]Binary Tree Preorder Traversal/二叉树的前序遍历

题目大意

二叉树前序遍历 挑战:迭代解题

解题思路

递归简单

迭代思路:见下方代码前

              1

       /     \

      2         3

    /     \    /    \

    4       5  6      7 

代码

递归

class Solution(object):
    def _preorderTraversal(self, root, result):
        if root:
            result.append(root.val)
            self._preorderTraversal(root.left, result)
            self._preorderTraversal(root.right, result)
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root == None:
            return []
        result = []
        self._preorderTraversal(root, result)
        return result

迭代

1.根节点入栈 2.取出节点,值加入结果,然后先加右,后加左。 3.重复2

注意:就算节点没有孩子,其指向孩子的指针(node.left)是None,不会报错

但是如果取值node.left.val,则会报错。所以最好是像要判断一下if node.left/right,因为这样栈中就不会有None,多浪费了时间。

while stack:
    node = stack.pop()
    if node:
        ret.append(node.val)
        stack.append(node.right)
        stack.append(node.left)

<precompiled.treenode.TreeNode object at 0x7f19ec21fc90>
None
None
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ret = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                ret.append(node.val)
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
        return ret

总结

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏王清培的专栏

zookeeper 实现分布式锁安全用法

标签: zookeeper sessionExpire connectionLoss 分布式锁

15520
来自专栏绿巨人专栏

Node JS World

The pluggable linting utility for JavaScript and JSX

15520
来自专栏编程微刊

微信小程序wepy框架入门教程(一)

端开发框架和环境都是需要 Node.js ,先安装node.js开发环境,WePY借鉴了Vue.js(后文简称Vue)的语法风格和功能特性,vue的运行是要依赖...

84230
来自专栏书山有路勤为径

认识ROS

1.节点(node)--软件模块 执行任务的进程 2.节点管理器(ROS Master)控制中心,提供参数管理 记录每个节点信息 3.话题(topic)...

26540
来自专栏C/C++基础

Linux硬链接与软链接

在Linux中,连接文件有两种,一种类似于Windows的快捷方式,可以让你快速地链接到目标文件(或目录),这种称为软链接(soft link),也叫作符号链接...

54320
来自专栏木子昭的博客

macOS Mojave 10.14安装nvm

nodejs的版本迭代非常快速, 时至今日(2019年2月7日), nodejs的最新版本是11.

9220
来自专栏刘晓杰

Android:CoolWeather天气查看器

但是由于网络地址的问题一直加载不出来,所以也没法通过安装查看。不过从这个软件还是可以学到很多东西。

12620
来自专栏编程坑太多

「实战篇」开源项目docker化运维部署-借助dockerSwarm搭建集群部署(九)

为了让学习的知识融汇贯通,目前是把所有的集群都放在了一个虚拟机上,如果这个虚拟机宕机了怎么办?俗话说鸡蛋不要都放在一个篮子里面,把各种集群的节点拆分部署,应该把...

10040
来自专栏前端vue

vue-cli3项目创建-配置-发布

(2) 修改user module -- src/store/module/user.js

4.3K40
来自专栏C/C++基础

Linux索引节点inode

理解inode,要从文件储存说起。文件储存在硬盘上,硬盘的最小存储单位叫做”扇区”(Sector)。每个扇区储存512字节(相当于0.5KB)。操作系统读取硬盘...

68830

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励