设二叉树共有 个结点，函数 preorderTraversal 的时间复杂度为O(n)，空间复杂度为O(n)。
1 class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7 def preorder(root, res):
8 if root is None:
9 return
10 res.append(root.val)
11 preorder(root.left, res)
12 preorder(root.right, res)
13 def preorderTraversal(root):
14 res = []
15 preorder(root, res)
16 return res
17
18
19 if __name__ == "__main__":
20
21 root = TreeNode(1)
22 root.right = TreeNode(2)
23 root.right.left = TreeNode(3)
24 result = preorderTraversal(root)
25 print("前序遍历结果：", result)