给定一个二叉树,返回它的 前序 遍历。
时间: 2023-08-27 22:04:02 浏览: 48
好的,这是一道二叉树的经典问题。前序遍历的顺序是:根节点 -> 左子树 -> 右子树。实现方式有两种:递归和迭代。
递归方法比较简单,代码如下:
```python
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res = [root.val]
res += self.preorderTraversal(root.left)
res += self.preorderTraversal(root.right)
return res
```
迭代方法需要用到栈,代码如下:
```python
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack, res = [root], []
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
```
以上是 Python 代码,其中 TreeNode 是二叉树的节点类,List[int] 表示返回一个整数列表。