前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[Leetcode][python]Binary Tree Preorder Traversal/二叉树的前序遍历

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

作者头像
蛮三刀酱
发布2019-03-26 17:04:03
4890
发布2019-03-26 17:04:03
举报
文章被收录于专栏:蛮三刀的后端开发专栏

题目大意

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

解题思路

递归简单

迭代思路:见下方代码前

代码语言:javascript
复制
              1

       /     \

      2         3

    /     \    /    \

    4       5  6      7 

代码

递归

代码语言:javascript
复制
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,多浪费了时间。

代码语言:javascript
复制
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
代码语言:javascript
复制
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

总结

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年08月03日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目大意
  • 解题思路
  • 代码
    • 递归
      • 迭代
      • 总结
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档