数据结构构建二叉树遍历

二叉树的遍历方式主要有三种：前序遍历、中序遍历和后序遍历。

前序遍历的顺序是：根节点 -> 左子树 -> 右子树，即先访问根节点，再访问左子树，最后访问右子树。

中序遍历的顺序是：左子树 -> 根节点 -> 右子树，即先访问左子树，再访问根节点，最后访问右子树。

后序遍历的顺序是：左子树 -> 右子树 -> 根节点，即先访问左子树，再访问右子树，最后访问根节点。

二叉树的遍历可以使用递归或者栈来实现。以前序遍历为例，递归实现的代码如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def preorderTraversal(root: TreeNode) -> List[int]:
    res = []
    def dfs(node):
        if not node:
            return
        res.append(node.val)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return res

栈实现的代码如下：

def preorderTraversal(root: TreeNode) -> List[int]:
    res = []
    stack = [root]
    while stack:
        node = stack.pop()
        if not node:
            continue
        res.append(node.val)
        stack.append(node.right)
        stack.append(node.left)
    return res

其中，递归实现中的dfs函数表示对以node为根节点的子树进行前序遍历，栈实现中的stack保存的是待访问的节点，先将右子节点入栈，再将左子节点入栈，以确保先访问左子树。