后序遍历二叉树 Posted on 2021-06-09 00:00:00 2022-04-12 00:00:00 by Author 摘要 后序遍历二叉树，除了用递归的方式，你还会其他的方式吗 # 后序遍历二叉树 > 写于2021/06/09 1. 后序遍历二叉树，一般用的是递归方法实现的，你可以使用非递归方式实现吗？(提示：使用栈） 2. 示例描述 - 示例一 - 输入： - 输出：[3, 2, 1] - 示例二 - 输入： - 输出：[7, 8, 3, 9, 6, 2, 1] 3. 解题思路 - 对于二叉树的后序遍历，我们都知道，先遍历一个节点的左孩子节点，再遍历这个节点的右孩子节点，然后在遍历该节点。（这里说的左孩子与右孩子又是一个二叉树，不要狭义的理解为该节点只有左孩子与右孩子还有该节点本身），对于该题我们可以想想，他的遍历顺序为：左右中，而前序遍历的顺序为：中左右，我们可以发现只要把前序遍历的稍微转变成：中右左顺序，然后在这个基础上逆转一下就成为：左右中就和后续遍历的顺序一样。但是如何实现这个尼？ - 我在前序遍历的算法中讲过，用栈进行解决这个问题，其中主要思想就是节点出栈后到底是左孩子先进栈还是右孩子先进栈。在前序遍历中我们知道当一个节点出栈后，右孩子先进栈，然后左孩子在进栈，因为栈的特点是先进后出，而我们先序遍历的就是需要先访问左孩子在访问右孩子，所以左孩子后进栈，那就先出栈，就先访问，符合我们的要求。而后续遍历，我们上一段我们讲过，我们把前序遍历顺序变为中右左的顺序，然后在逆转一下就能实现。那么我们是不是可以在前序遍历中，一个节点出栈后，加入左右孩子顺序这个地方做一点文章尼。答案是的。即就是，该节点先出栈，然后先进左孩子，然后在进右孩子(前提是这两个左右孩子都存在的情况下，如果木有，就不进栈了呗)，这和先序遍历的时候左右孩子进栈的顺序刚好相反，也就实现我们在先序遍历上稍作变化的操作，然后后续的操作和先序遍历的情况差不多，就是左右孩子进栈顺序不一样罢了。最后按照以上步骤遍历完成了一颗二叉树，那么我们在把该结果逆序输出就得出二叉树的后序遍历了。 - 这里就拿示例二的输入进行说明吧。我们首先按照先序遍历中稍作改变的情况下输出来的结果为：[1, 2, 6, 9, 3, 8, 7]，而我们实际上想要的结果为：[7, 8, 3, 9, 6, 2, 1]，然后我们把稍作改变的结果逆序输出就阔以了。接下来我们就看看代码的具体实现吧，每一步都有详细的注释。 4. 代码实现 ```java public List<Integer> postorderTraversal(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.left != null) stack.add(treeNode.left); //否则就加入右孩子到栈中 if (treeNode.right != null) stack.add(treeNode.right); } //逆转结果集 Collections.reverse(result); //返回最终结果 return result; } ```
{{ item.content }}
{{ child.content }}