如何用迭代法从有序数组构建平衡BST？求Java实现

为什么迭代法需要栈/队列？ #

递归构建时，系统会自动用调用栈保存每一步的上下文：比如当前要处理的数组区间[start, end]、当前节点的父节点，以及这个节点是父节点的左孩子还是右孩子。当递归到叶子节点后，系统会自动回溯到上一层，继续处理剩下的区间。

迭代法没有系统栈帮我们做这些，所以必须手动用栈/队列存储这些上下文信息，否则处理完一个区间的根节点后，没法回到之前的状态去处理左、右子树对应的子区间。栈是最常用的，因为递归本身就是深度优先的，栈的后进先出特性刚好匹配递归的回溯顺序。

为什么迭代法比递归复杂且不常用？ #

1. 递归更贴合分治逻辑：构建平衡BST的核心是分治——每次取中位数当根，再递归处理左右子数组。递归代码直接对应这个逻辑，几乎是“翻译”思路，简洁易懂。
2. 迭代需要手动维护上下文：你得自己定义数据结构来存区间、父节点、左右标识，还要手动控制栈的压入弹出，代码量翻倍，逻辑也更绕，容易出错。
3. 递归栈深度可控：对于有序数组构建平衡BST，递归的栈深度是logN（树的高度），远小于Java默认的栈大小，不会出现栈溢出问题。所以除非是极端大数组（实际很少见），递归完全够用。

Java代码实现迭代法 #

首先定义Node类：

class Node {
    int val;
    Node left;
    Node right;
    Node parent;

    Node(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

然后是迭代构建的核心代码，用栈存储每个待处理的区间上下文：

import java.util.Stack;

public class BalancedBST {
    // 辅助类：存储待处理的区间信息和父节点关联
    static class StackFrame {
        int start;
        int end;
        Node parent;
        boolean isLeftChild; // 标记当前区间要生成的节点是父节点的左还是右孩子

        StackFrame(int start, int end, Node parent, boolean isLeftChild) {
            this.start = start;
            this.end = end;
            this.parent = parent;
            this.isLeftChild = isLeftChild;
        }
    }

    public static Node sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }

        Stack<StackFrame> stack = new Stack<>();
        // 初始处理整个数组区间，根节点没有父节点
        stack.push(new StackFrame(0, nums.length - 1, null, false));
        Node root = null;

        while (!stack.isEmpty()) {
            StackFrame frame = stack.pop();
            int start = frame.start;
            int end = frame.end;

            if (start > end) {
                continue;
            }

            // 取中位数作为当前节点的值，避免溢出
            int mid = start + (end - start) / 2;
            Node currentNode = new Node(nums[mid]);

            // 连接到父节点
            if (frame.parent == null) {
                root = currentNode;
            } else {
                currentNode.parent = frame.parent;
                if (frame.isLeftChild) {
                    frame.parent.left = currentNode;
                } else {
                    frame.parent.right = currentNode;
                }
            }

            // 栈是后进先出，先压右区间再压左区间，保证左子树先处理
            stack.push(new StackFrame(mid + 1, end, currentNode, false));
            stack.push(new StackFrame(start, mid - 1, currentNode, true));
        }

        return root;
    }

    // 测试用例：中序遍历验证是否正确
    public static void inorderTraversal(Node root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }

    public static void main(String[] args) {
        int[] nums = {-10, -3, 0, 5, 9};
        Node root = sortedArrayToBST(nums);
        inorderTraversal(root); // 输出：-10 -3 0 5 9
    }
}

代码说明：

• StackFrame类用来保存每个待处理区间的起始、结束索引，父节点，以及当前节点是父节点的左/右孩子。
• 栈的处理顺序：先压右区间，再压左区间，这样弹出时会先处理左区间，和递归的先左后右顺序一致，保证树的结构正确。
• 每次取中位数创建节点，然后连接到父节点的对应位置，再把左右子区间压入栈继续处理。

内容的提问来源于stack exchange，提问作者Oreo