二叉树后序遍历算法多种实现傻傻分不清楚

二叉树后序遍历算法多种实现傻傻分不清楚

引用

CSDN

1.

https://blog.csdn.net/cxsjabcabc/article/details/137507832

二叉树的后序遍历是一种重要的树遍历策略，按照"左子树-》右子树-》根节点"的顺序访问节点。这种遍历方式在编程中可以通过递归或非递归的方式实现。本文将详细介绍二叉树后序遍历的多种实现方法，包括递归算法和三种非递归算法（单栈法、双栈法、栈+双向队列法），并提供Java代码示例。

1. 介绍

二叉树的后序遍历是一种遍历二叉树的策略，按照"左子树-》右子树-》根节点"的顺序访问节点的子树或根节点。具体来说，后序遍历首先访问左子树，然后访问右子树，最后访问根节点。

这种遍历方式在编程中可以通过递归或非递归的方式进行实现。通常来说，递归算法较容易理解，但可能会造成栈溢出，而非递归算法较难理解。

2. 代码实现

以下以Java编程语言为例。

2.1 二叉树节点的数据结构定义

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    TreeNode(int value) {
        this.value = value;
    }
}

2.2 后序遍历递归算法代码

public void postOrderTraversalRecursive(TreeNode root){
    // 若root节点为空，则子遍历完成
    if(null==root){
        return ;
    }
    // 先递归遍历左子树
    postOrderTraversalRecursive(root.left);
    // 再递归遍历右子树
    postOrderTraversalRecursive(root.right);
    // 最后访问根节点
    System.out.println(root.value);
}

2.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;
        }
    }
}

2.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 + " ");
    }
}

2.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;
}