深度优先遍历类似二叉树的

深度优先遍历（Depth First Search，DFS）是一种图遍历算法，类似于二叉树的前序遍历。在深度优先遍历中，从某个顶点开始，沿着一条路径不断向下遍历，直到无法继续为止，然后回溯到前一个结点，继续向下遍历其它路径，直到所有的结点都被访问过为止。

类似于二叉树的前序遍历，深度优先遍历也有递归和非递归两种实现方式。递归实现的深度优先遍历类似于二叉树的前序遍历，非递归实现的深度优先遍历需要借助栈来实现。

相关问题

深度优先搜索遍历和二叉树遍历

深度优先搜索（DFS）遍历和二叉树遍历是两个不同的概念。

深度优先搜索遍历（DFS）是一种用于图或树的遍历算法。它从起始节点开始，沿着路径尽可能深地探索直到无法继续，然后回溯到上一个节点继续探索其他路径。DFS 可以分为前序遍历、中序遍历和后序遍历三种方式。在前序遍历中，先访问当前节点，然后递归地访问左子树和右子树。在中序遍历中，先递归地访问左子树，然后访问当前节点，最后递归地访问右子树。在后序遍历中，先递归地访问左子树和右子树，最后访问当前节点。

二叉树遍历是指按照某种顺序访问二叉树的所有节点。二叉树的遍历方式有多种，包括前序遍历、中序遍历和后序遍历。前序遍历的顺序是：根节点 -> 左子树 -> 右子树；中序遍历的顺序是：左子树 -> 根节点 -> 右子树；后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

可以看出，DFS 是一种遍历算法，而二叉树遍历是一种具体应用于二叉树的遍历方式。DFS 可以用于遍历非二叉树的图结构，而二叉树遍历则只适用于二叉树。

深度优先前序遍历二叉树代码

深度优先前序遍历二叉树是一种常用的遍历方式，它的代码实现如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorderTraversal(root):
    if root is None:
        return []
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

上述代码中，我们使用了一个栈来辅助实现深度优先前序遍历。首先，我们将根节点入栈。然后，从栈中弹出一个节点，将其值加入结果列表中，并依次将右子节点和左子节点入栈。重复这个过程，直到栈为空。