怎么解析python二叉树的后序遍历

怎么解析python二叉树的后序遍历，针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

二叉树的后序遍历

题目

给定一个二叉树，返回它的 后序 遍历。

 

示例:

输入: [1,null,2,3]

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解题思路

用栈(Stack)的思路来处理问题。

后序遍历的顺序为左-右-根，具体算法为：

• 先将根结点压入栈，然后定义一个辅助结点head

• while循环的条件是栈不为空

• 在循环中，首先将栈顶结点t取出来

• 如果栈顶结点没有左右子结点，或者其左子结点是head，或者其右子结点是head的情况下。我们将栈顶结点值加入结果res中，并将栈顶元素移出栈，然后将head指向栈顶元素

• 否则的话就看如果右子结点不为空，将其加入栈

• 再看左子结点不为空的话，就加入栈

动画演示

动画演示GIF加载有点慢，请稍等片刻加载显示^_^

参考代码

补充

下面这种写法使用了一个辅助结点p，这种写法其实可以看作是一个模版，对应的还有前序和后序的模版写法，形式很统一，方便于记忆。上上篇更新前序的和上篇更新的中序文章中都会补充该写法。思路与代码如下：

• 先将先序遍历的根-左-右顺序变为根-右-左

• 再翻转变为后序遍历的左-右-根，翻转还是改变结果res的加入顺序

• 然后把更新辅助结点p的左右顺序换一下即可

关于怎么解析python二叉树的后序遍历问题的解答就分享到这里了，希望以上内容可以对大家有一定的帮助，如果你还有很多疑惑没有解开，可以关注亿速云行业资讯频道了解更多相关知识。