GuilinDev

Lc0173

05 August 2008

173 - Binary Search Tree Iterator

原题概述

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling ‘next()’ will return the next smallest number in the BST.

Note: ‘next()’ and ‘hasNext()’ should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

题意和分析

这道题是对二叉搜索树的遍历，要求next()返回下一个最小的val，next()和hasNext()的时间复杂度为O(1)，空间复杂度要求为O(h)，其中h为高度。BST的建树规则是left-root-right，这个跟中序遍历一样。

每个节点的val值大于左子节点，小于右子节点。注意它不一定是完全的二叉树。所有结点的val值是唯一的。数组的搜索比较方便，可以直接使用下标，但删除或者插入就比较麻烦了，而链表与之相反，删除和插入都比较简单，但是查找很慢，这自然也与这两种数据结构的存储方式有关，数组是取一段相连的空间，而链表是每创建一个节点便取一个节点所需的空间，只是使用指针进行连接，空间上并不是连续的。而二叉树就既有链表的好处，又有数组的优点。

中序遍历的顺序是GDHBEAKCIJF

使用自定义的栈来模拟中序遍历。也就是说，我们将采用迭代的方式来模拟中序遍历，而不是采用递归的方法；这样做的过程中，能够轻松的实现这两个函数的调用，而不是用其他额外的空间。

然而，就这两个函数的复杂性而言，会有点复杂，我们需要花一些时间来理解这种方法是否符合问题所说的渐近复杂性的要求。具体算法：

  1. 初始化一个空栈 S，用于模拟二叉搜索树的中序遍历。中序遍历采用与递归相同的方法，只是现在使用的是自己的栈而不是系统的堆栈。由于使用自定义的数据结构，因此可以随时暂停和恢复递归。
  2. 还要实现一个帮助函数_leftmostInorder，在实现中将一次又一次的调用它。这个函数将给定节点中的所有左子节点添加到栈中，直到节点没有左子节点为止。
  3. 第一次调用 next() 函数时，必须返回二叉搜索树的最小元素，然后模拟递归必须向前移动一步，即移动到二叉搜索树的下一个最小元素上。栈的顶部始终包含 next() 函数返回的元素。hasNext() 很容易实现，因为只需要调用stack的方法直接检查栈是否为空。
  4. 首先，给定二叉搜索树的根节点，我们调用函数 _leftmostInorder，这确保了栈顶部始终包含了 next() 函数返回的元素。
  5. 假设调用 ‘next()’，我们需要返回二叉搜索树中的下一个最小元素，即栈的顶部元素。有两种可能性：
    • 一个是栈顶部的节点是一个叶节点。这是最好的情况，因为我们什么都不用做，只需将节点从栈中弹出并返回其值。所以这是个常数时间的操作。
    • 另一个情况是栈顶部的节点拥有右节点。我们不需要检查左节点，因为左节点已经添加到栈中了。栈顶元素要么没有左节点，要么左节点已经被处理了。如果栈顶部拥有右节点，那么我们需要对右节点上调用帮助函数。该时间复杂度取决于树的结构。
  6. ‘next()’ 函数调用中，获取下一个最小的元素不需要花太多时间，但是要保证栈顶元素是 ‘next()’ 函数返回的元素方面花费了一些时间。

代码

  • 时间复杂度：
    • hasNext()：若栈中还有元素，则返回 true，反之返回 false。所以这是一个 O(1) 的操作。
    • next()：包含了两个主要步骤。一个是从栈中弹出一个元素，它是下一个最小的元素。这是一个 O(1) 的操作。然而，随后我们要调用帮助函数 _leftmostInorder，它需要递归的，将左节点添加到栈上，是线性时间的操作，最坏的情况下为 O(N)。但是只对含有右节点的节点进行调用，它也不会总是处理 N 个节点。只有当有一个非常不平衡的树，才会有 N 个节点。因此该操作的平均时间复杂度仍然是 O(1)，符合问题中所要求的。
  • 空间复杂度：O(h)O(h)，使用了一个栈来模拟递归。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {
    
    Stack<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        
        this._leftmostInorder(root);
    }
    
    private void _leftmostInorder(TreeNode node) {
        while (node != null) {
            // 将给定的node的所有左孩子节点放入到stack中
            this.stack.push(node);
            node = node.left;
        }
    }
    
    /** @return the next smallest number */
    public int next() {
        if (hasNext()) {
            TreeNode topmost = this.stack.pop();
            
            // 根据BST的特征，如果当前节点需要返回，需要把当前节点的右儿子的所有左子树push到stack中
            // 这时候当前节点的左子树已经pop完，仔细想想为什么
            if (topmost.right != null) {
                this._leftmostInorder(topmost.right);
            }
            
            return topmost.val;
        }
        return new Integer(null); // 为空了
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        // 直接调用原生方法进行判断是否还有元素
        return this.stack.size() > 0;
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */
This site is open source. Improve this page.