二叉树后序遍历算法多种实现傻傻分不清楚
致力于C、C++、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等编程技术的技巧经验分享。
若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢。您的支持是我们为您提供帮助的最大动力。
1.介绍
二叉树的后序遍历是一种遍历二叉树的策略，按照"左子树-》右子树-》根节点"的顺序访问节点的子树或根节点。具体来说，后序遍历首先访问左子树，然后访问右子树，最后访问根节点。
这种遍历方式在编程中可以通过递归或非递归的方式进行实现。
通常来说，递归算法较容易理解，但可能会造成栈溢出，而非递归算法较难理解。
以下用代码实现后序遍历。
2.代码
以下以Java编程语言为例。
1）二叉树节点的数据结构定义如下：
class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
}
}
2）后序遍历递归算法代码
public void postOrderTraversalRecursive(TreeNode root){
//若root节点为空，则子遍历完成
if(null==root){
return ;
}
//先递归遍历左子树
postOrderTraversalRecursive(root.left);
//再递归遍历右子树
postOrderTraversalRecursive(root.right);
//最后访问根节点
System.out.println(root.value);
}
3）后序遍历非递归算法代码（单栈法）
可以使用栈来模拟递归过程。此例只用到了一个栈，所以叫做单栈法。
后序遍历与前序遍历和中序遍历存在差异。即我们在访问左子树之后需要访问右子树，然后才能再访问根节点，所以我们的根节点不能在访问左子树之后出栈，而是需要继续访问右子树，当我们右子树访问完成之后再出栈。
public void postOrderTraversalNonRecursive(TreeNode root)
{
//存储遍历过程中的需要继续处理的临时节点
Stack<TreeNode> stack = new Stack<>();
//保存临时根节点，从root开始
TreeNode node =root;
//保存上次访问的节点，从root开始
TreeNode lastVisit = root;
//临时节点不为空或者栈不为空时需要继续处理
while(null != node || !stack.empty())
{
while(null != node){
//存储临时节点到栈中
stack.push(node);
//继续遍历左子树
node = node.left;
}
//查看当前栈顶元素
node = stack.peek();
//如果当前栈顶元素的右子树为空，或者右子树已经被访问，则说明左右节点都访问完成了
//则可以直接输出当前节点的值
if(null == node.right || node.right==lastVisit){
//左子树与右子树都访问完成后输出当前根节点的值
System.out.println(node.value+" ");
//当前节点已处理完成，从栈中弹出，继续下一轮遍历
stack.pop();
//更新上次访问的节点
lastVisit=node;
//左子树右子树根节点都访问完毕后，将临时节点置空，从而从栈中处理下一个节点
node=null;
}else{
//右子树尚未被访问，则继续遍历右子树
node=node.right;
}
}
}
4）后序遍历非递归算法代码（双栈法）
由于后序遍历的输出顺序是左->右->根，倒过来就是根->右->左。因此利用栈（先进后出FILO，与正常顺序是反的）的性质，只需要按照根->右->左的访问顺序访问一次，并存入栈中，最后从栈顶输出所有栈节点就可以了。
算法需要两个栈，一个是正常遍历需要的栈，一个是存储倒过来的元素的栈，所以也叫双栈法。
public static void postOrderTraversalNonRecursive2Stack(TreeNode root) {
//后序遍历中存储正常访问顺序的栈
Stack<TreeNode> stack = new Stack<TreeNode>();
//后序遍历中存储逆向访问顺序的栈
Stack<TreeNode> output = new Stack<TreeNode>();
TreeNode node = root;
//判断是否还有节点需要处理
while (null != node || !stack.isEmpty()) {
if (null != node) {
//先访问根节点，压入栈中
stack.push(node);
output.push(node);
//再访问右子节点
node = node.right;
} else {
//再访问左子节点
node = stack.pop();
node = node.left;
}
}
//从栈顶开始输出栈里元素的值，即输出正常访问顺序栈stack的倒序结果output栈，即为最终结果
while (output.size() > 0) {
TreeNode n = output.pop();
System.out.print(n.value + " ");
}
}
5）后序遍历非递归算法代码（Stack+Deque，即栈+双向队列法）
算法的数据结构里，一个存储正常遍历需要的栈，一个存储最终输出的元素双端队列列表，所以也叫栈+双向队列法。
public List<TreeNode> postOrderTraversalNonRecursiveStackDeque(TreeNode root) {
//保存计算出的最终结果列表
LinkedList<TreeNode> result = new LinkedList<>();
//若root节点为空，则遍历完成
if (null == root) {
return result;
}
//后序遍历中存储正常访问顺序的栈
Stack<TreeNode> stack = new Stack<>();
//压入根节点到栈中
stack.push(root);
//存储当前节点
TreeNode curNode;
//若栈中有数据，则继续处理
while(!stack.isEmpty()) {
//获取当前栈顶元素
curNode = stack.pop();
//将栈顶元素插入到结果列表LinkedList的头部
result.addFirst(curNode.value);
if (null != curNode.left) {
//压入左子节点到栈中
stack.push(curNode.left);
}
if (null != curNode.right) {
//压入右子节点到栈中
stack.push(curNode.right);
}
}
return result;
}
若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢。您的支持是我们为您提供帮助的最大动力。
