144. 二叉树的前序遍历
image-20201208190400120
递归写法
前序遍历顺序就是 根节点->左节点->右节点
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: node = [] self.order(root, node) return node def order(self, root, node): if root is None: return node.append(root.val) self.order(root.left, node) self.order(root.right, node)
迭代写法
通过一个栈来维护节点的输出顺序，每次出一个节点，把节点的值拿出来放到结果数组里，请注意栈是先进后出。 所以先进right节点，到时候先出的就是left节点。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: if root is None: return [] stack = [root] ans = [] while len(stack) > 0: current = stack.pop() ans.append(current.val) if current.right is not None: stack.append(current.right) if current.left is not None: stack.append(current.left) return ans
image-20201208191239586
