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

xiaoxiao2021-02-28  24

## 解题思路

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

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