基本概念
要解决这道题首先得了解二叉树前序遍历
前序遍历
以下面这个二叉树为例,前序遍历的遍历顺序为根节点->左子节点->右子节点:
前序遍历一切都以左子节点为优先,即遍历结果为1 2 4 5 3 6 7
递归解法
递归解法十分简单,直接上代码了
代码
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
def preorder(root:TreeNode):
if not root: return
res.append(root.val)
root.left = preorder(root.left)
root.right = preorder(root.right)
res = []
preorder(root)
return res
迭代解法
算法过程
- 初始化栈,并将根节点入栈
- 当栈不为空时:
- 弹出栈顶元素node,并将值添加到结果
res
中。 - 如果node的右子树非空,将右子树入栈
- 如果node的左子树非空,将左子树入栈
- 弹出栈顶元素node,并将值添加到结果
因为栈先进后出的特性,所以需要先将右子树入栈再将左子树入栈来保证根节点->左节点->右节点的顺序
代码
# 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 not root: return []
res = []
stack = [root]
while stack:
cur = stack.pop()
res.append(cur.val)
if cur.right: stack.append(cur.right)
if cur.left: stack.append(cur.left)
return res