JAVA中以先根次序非递归遍历二叉树

可以使用栈来实现二叉树的先根次序非递归遍历，具体的实现方法是：先将根节点入栈，然后开始循环，如果栈不为空，则弹出栈顶元素，访问该节点，并依次将其右子节点和左子节点入栈。重复执行这个循环，直到栈为空。这样就完成了二叉树的先根次序非递归遍历。

相关问题

JAVA中以先根次序非递归遍历二叉树的程序

以下是JAVA中以先根次序非递归遍历二叉树的程序：

public void preOrderTraversal(Node root) {
    if (root == null) return;
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node curr = stack.pop();
        System.out.print(curr.val + " ");
        if (curr.right != null) stack.push(curr.right);
        if (curr.left != null) stack.push(curr.left);
    }
}

该程序使用栈实现先根次序非递归遍历二叉树。具体来说，程序首先将根节点入栈，然后循环执行以下操作：弹出栈顶节点并输出其值，将其右儿子（如果有）入栈，将其左儿子（如果有）入栈。由于先入栈左儿子，再入栈右儿子，所以在下次循环时会先访问左子树。这样，就可以实现以先根次序遍历二叉树的效果。

非递归后序遍历二叉树

### 非递归后序遍历二叉树的实现

对于非递归方式实现二叉树的后序遍历，可以采用栈结构来模拟递归调用过程。具体做法如下：

在该方法中，使用一个栈保存节点，并按照根节点先于子节点访问的原则压入栈内。为了适应后序遍历的要求——即左子树->右子树->根节点这一顺序，在每次弹出元素时将其值插入到列表头部位置，从而实现了反向存储的结果集。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if (root == null) return list;
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            root = stack.pop();
            list.add(0, root.val); // 将当前结点值添加至链表首部
            
            if (root.left != null) {
                stack.push(root.left);
            }
            
            if (root.right != null) {
                stack.push(root.right);
            }
        }

        return list;
    }
}

上述代码展示了如何利用Java中的`Stack`类以及`LinkedList`作为返回容器完成整个操作流程[^3]。

另外一种思路是通过两次反转的方法来进行处理：第一次正常前序遍历时改变左右孩子的入栈次序；第二次再整体翻转最终得到的数据序列即可获得正确的后序遍历结果。

Python版本同样适用此逻辑：

def postorderTraversal(self, root: TreeNode) -> List[int]:
    result = []
    if not root:
        return []

    stack = [root]

    while stack:
        node = stack.pop()
        result.insert(0, node.val)

        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    return result

这两种方案都能有效地解决非递归形式下的二叉树后序遍历问题[^4]。