二叉树非递归后序遍历（java）

╰半夏微凉° 2023-07-13 13:53 88阅读 0赞

// 非递归后序遍历
public static void postorderTraversal(TreeNode root) { 
    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
    TreeNode node = root;
    TreeNode lastVisit = root;//设置游标判断右子树
    while (node != null || !treeNodeStack.isEmpty()) { //如果节点不为空且栈不为空
        while (node != null) { //如果节点不为空
            treeNodeStack.push(node);//将节点入栈
            node = node.left;//先看左子树
        }
        node = treeNodeStack.peek();//查看栈顶元素
        //如果其右子树也为空，或者右子树已经访问
        //则可以直接输出当前节点的值
        if (node.right == null || node.right == lastVisit) { 
            System.out.print(node.val + " ");
            treeNodeStack.pop();//出栈
            lastVisit = node;//将当前节点设为游标
            node = null;//节点设为空
        } else { //如果其右子树不为空，以及右子树未访问
            node = node.right; //否则，继续遍历右子树
        }
    }
}