二叉树的迭代后序遍历

Question

我试图解决 LeetCode 上的Q145，它基本上要求你用后序方法遍历二叉树。

使用递归编写代码没有任何挑战，但迭代方法需要一些计算。

虽然我有一个我认为有效的解决方案，但 LeetCode 不接受它，因为出现了“超出内存限制”的错误。

有什么方法可以进一步简化我提出的解决方案吗？

public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}


//*******************************************


public List<Integer> postorderTraversalIterative (TreeNode root) {


        List <Integer> list = new ArrayList<>();
        Stack <TreeNode> stack = new Stack<>();

        TreeNode currentNode = root;
        int visited = 0;

        while (!stack.isEmpty() || currentNode!=null) {

            while (currentNode!=null) {
                stack.push(currentNode);
                currentNode = currentNode.left;
            }

            currentNode = stack.pop();

            if (currentNode.right == null) {
                list.add(currentNode.val);
            }

            else {

                if (visited==0) {
                    stack.push(currentNode);
                    visited = 1;
                }

                else {
                    list.add(currentNode.val);
                    currentNode = null;
                    visited=0;
                }
            }

            if (currentNode!=null) {
                currentNode = currentNode.right;
            }
        }

        return list;
}

更大的 else 块（和变量 visited）基本上是为了确保一旦右子节点被遍历，具有右子节点的节点就会被添加到 list 中。

Answer 1

这样的事情适合你吗？如果没有，请分享我的错误，以便我能够改正。

public List<Integer> postorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(0, node.val); // Add node value to the front of the list

        // Push left child first, then right child
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }

    return result;
}