前往此题

基本概念

要解决这道题首先得了解二叉树前序遍历

前序遍历

以下面这个二叉树为例,前序遍历的遍历顺序为根节点->左子节点->右子节点:

前序遍历一切都以左子节点为优先,即遍历结果为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

迭代解法

算法过程

  1. 初始化栈,并将根节点入栈
  2. 当栈不为空时:
    • 弹出栈顶元素node,并将值添加到结果res中。
    • 如果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