[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

总结

后端技术漫谈 认证博客专家 分布式 Linux Java 我是一名后端开发工程师。主要关注后端开发，数据安全，爬虫，物联网，边缘计算等方向，欢迎交流。各大平台都可以找到我：- 微信公众号：后端技术漫谈- Github：@qqxx6661- ：@蛮三刀把刀- 知乎：@后端技术漫谈- 简书：@蛮三刀把刀- 掘金：@蛮三刀把刀- 腾讯云+社区：@后端技术漫谈原创文章主要内容：- 后端开发- Java面试- 设计模式/数据结构/算法题解- 爬虫/边缘计算/物联网- 读书笔记/逸闻趣事/程序人生