二叉树的遍历算法之先序遍历

我们先来熟悉一下二叉树的概念二叉树是‌每个节点最多有两个子树‌的树形数据结构通常分为左子树和右子树。先序遍历先序遍历就是先访问根节点然后遍历左子树最后遍历右子树。二叉树的先序遍历的递归实现该版本是二叉树深度优先搜索最常见的实现方式。其基本思路是访问当前节点。递归遍历当前节点的左子树。由于栈的先进后出性质所以先将右子树入栈后将左子树入栈出栈的时候是左子树先出栈右子树后出栈符合先序遍历的顺序。递归遍历当前节点的右子树。def dfs_preorder(root): if root is None: return print(root.val) # 访问当前节点。 dfs_preorder(root.left) # 递归遍历当前节点的左子树。 dfs_preorder(root.right) # 递归遍历当前节点的右子树。