题目描述

设计并实现一个二叉搜索树迭代器类，该类需要包含以下功能：

• BSTIterator(TreeNode root)：构造函数，接收一个二叉搜索树的根节点 root 作为输入，并初始化迭代器。
• next()：返回二叉搜索树中的下一个最小元素（即中序遍历的下一个节点值）。
• hasNext()：检查迭代器中是否还有元素。如果有，则返回 true；否则返回 false。

注意：

• 你只能使用给定的 TreeNode 类型的节点。
• 你可以假设 next() 和 hasNext() 的调用总是有效的，即调用它们时，树中至少存在一个元素。

示例代码

以下是使用 PHP、Python 和 JavaScript 编写的示例代码：

PHP 示例

<?php
class TreeNode {
    public $val;
    public $left;
    public $right;

    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class BSTIterator {
    private $stack;

    function __construct($root) {
        $this->stack = new SplStack();
        $this->pushLeft($root);
    }

    private function pushLeft($node) {
        while ($node !== null) {
            $this->stack->push($node);
            $node = $node->left;
        }
    }

    function next() {
        $node = $this->stack->pop();
        $this->pushLeft($node->right);
        return $node->val;
    }

    function hasNext() {
        return !$this->stack->isEmpty();
    }
}

// 使用示例
$root = new TreeNode(7);
$root->left = new TreeNode(3);
$root->right = new TreeNode(15);
$root->right->left = new TreeNode(9);
$root->right->right = new TreeNode(20);

$iterator = new BSTIterator($root);
while ($iterator->hasNext()) {
    echo $iterator->next() . " ";
}
// 输出应为：3 7 9 15 20
?>

Python 示例

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self.pushLeft(root)

    def pushLeft(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def next(self):
        node = self.stack.pop()
        self.pushLeft(node.right)
        return node.val

    def hasNext(self):
        return len(self.stack) > 0

# 使用示例
root = TreeNode(7)
root.left = TreeNode(3)
root.right = TreeNode(15)
root.right.left = TreeNode(9)
root.right.right = TreeNode(20)

iterator = BSTIterator(root)
while iterator.hasNext():
    print(iterator.next(), end=" ")
# 输出应为：3 7 9 15 20

JavaScript 示例

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class BSTIterator {
    constructor(root) {
        this.stack = [];
        this.pushLeft(root);
    }

    pushLeft(node) {
        while (node) {
            this.stack.push(node);
            node = node.left;
        }
    }

    next() {
        const node = this.stack.pop();
        this.pushLeft(node.right);
        return node.val;
    }

    hasNext() {
        return this.stack.length > 0;
    }
}

// 使用示例
const root = new TreeNode(7);
root.left = new TreeNode(3);
root.right = new TreeNode(15);
root.right.left = new TreeNode(9);
root.right.right = new TreeNode(20);

const iterator = new BSTIterator(root);
while (iterator.hasNext()) {
    console.log(iterator.next());
}
// 输出应为：3 7 9 15 20

以上代码展示了如何在 PHP、Python 和 JavaScript 中实现一个二叉搜索树迭代器，按照中序遍历的顺序返回节点值。这些实现都利用了栈来辅助完成中序遍历的非递归实现。