前序遍历二叉树 Posted on 2021-06-07 00:00:00 2021-06-26 00:00:00 by Author 摘要 前序遍历二叉树，除了用递归的方式，你还会其他的方式吗 # 前序遍历二叉树(不用递归你会吗) > 写于2021/06/07 1. 题目描述 - 前序遍历二叉树，一般用的是递归方法实现的，你可以使用非递归方式实现吗？(提示：使用栈） 2. 示例描述 - 示例一 - 输入：  - 输出：[1, 2, 3] - 示例二 - 输入：  - 输出： [1, 2, 3, 7, 8, 6, 9] 3. 解题思路 - 对于前序遍历二叉树用递归写法，主要的代码用四行就可以完成了，但是如果不让使用递归的方式，那我们可以用其他的方式去解决吗？答案是可以的。我们可以手动去模拟一下二叉树的前序遍历的过程，然后感受一下他具体的遍历过程，看看我们可以用其他类型的数据结构去实现这个算法吗。下面咋们一起来手动试试。 - 首先我们用示例描述的示例二的这颗二叉树来进行模拟。首先我们拿到根节点`1`,然后没有左孩子，那就看右孩子，这次来到节点`2`的这个位置，这个节点有左右孩子，因为是先序遍历，所以我们肯定去找节点`2`的左孩子`3` ,节点`3`又有左右孩子，所以我们就继续来到节点`7`这个位置，节点`7`这个节点木有左右孩子，说明节点`3`的左孩子遍历完成了，那就要返回到节点`3`去遍历该节点的右孩子，然后到`8`这个节点，节点`8`没有左右孩子那么节点`3`遍历完成，又返回节点`2`的位置，继续遍历节点`2`的右孩子，之后步骤是差不多的，不在赘述，这里我们可能体会到一点回溯递归的思想了，但是本题要求不用递归的方法。以上的描述有可能太枯燥乏味，那我们用一个图来说明吧！（这个图是来源于代码随想录公众号，我所有的题解都是理解了他的思想之后，用我自己的话表述出来的，大家可以关注一波，保证不亏） -  - 看了上面的图之后，是不是有点感觉了。那我们根据动画可以看出，实现本算法非递归的方法实现的时候使用的数据结构是栈，我这样说可能有点牵强，有人可能会问，为啥使用栈，你咋知道使用栈的，其实我之前也是想不出来用栈的，也是看了题解才知道的，所以不要问我为什么了，问了就是我不会，哈哈哈哈哈哈哈嗝！咋们继续看这个动画，首先节点`5`进栈了，它有左右孩子，我们都晓得前序遍历先访问左孩子，在访问右孩子，如果我们左孩子先进栈，那么出栈的时候比右孩子后出来，那么就不是前序遍历。所以首先我们让根节点先进栈，然后在出栈，这样根节点就遍历了，但是在出栈之前，我们还要判断该节点是否有左右孩子，如果有，那么先进右孩子，然后在进左孩子，那么之后就没有这个根节点啥事了，因为该节点出栈了，并且他把他的左右孩子祸害了，给压入栈中了，此时栈中只有6和4这两个节点，节点4在栈顶，然后节点4和刚才讲的根节点操作的方式一样，出栈，然后在祸害右左孩子。然后重复之前的所有操作，直到栈中没有元素了，那么前序遍历也就完成了。其实讲了这么多，我感觉我自己讲的也是模棱两可，具体实践还是需要自己动手画一下，接下来就看看代码实现吧，每步都能有解释，具体实现看一下代码。 4. 代码实现 ```java public List<Integer> preorderTraversal(TreeNode root) { //定义返回结果集 List<Integer> result = new ArrayList<>(); //定义一个栈，栈中元素类型为节点类型 Stack<TreeNode> stack = new Stack<>(); //如果根节点为空，直接返回结果 if(root == null){ return result; } //首先根节点入栈，方便后续的操作 stack.push(root); //栈不为空，就一直重复遍历 while (!stack.isEmpty()){ //首先出栈顶的元素，用一个临时遍历接受 TreeNode treeNode = stack.pop(); //因为遍历，所以把该节点的只加入结果集中 result.add(treeNode.val); //如果右孩子不为空，那么先加入右孩子到栈中 if(treeNode.right!=null) stack.add(treeNode.right); //否则就加入左孩子到栈中 if(treeNode.left!=null) stack.add(treeNode.left); } //返回最终结果 return result; } ```
{{ item.content }}
{{ child.content }}