leetcode：173. 二叉搜索树迭代器

题目来源

• leetcode：173. 二叉搜索树迭代器

题目描述

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class BSTIterator {
public:
    BSTIterator(TreeNode* root) {

    }

    int next() {

    }

    bool hasNext() {

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

题目解析

这道题本质上考的是「将迭代版的中序遍历代码」做等价拆分。

使用栈模拟递归

• 涉及迭代器的时候，应该避免提前把所有的值都遍历出来，最好能够在迭代时计算next节点
• 一般来讲，我们遍历二叉树，基本都是用递归，如果要把递归转成迭代，基本想法就是用栈。

我们来看个具体的例子，实际访问节点的顺序是：

• 从 根节点12 开始一路到底遍历到所有左节点，路径保存到栈中；此时栈为 [12, 6, 5]。
• 弹出栈顶节点，即 叶子节点5 ；
• 下一个栈顶元素是 该叶子节点 的 根节点6；
• 然后把 该新的根节点的右子树9 一路到底遍历其所有左节点；栈为 [12, 9, 8, 7]。
• 继续运行下去，直到栈为空。
  

根据上面的遍历顺序，我们得出迭代的思路：

• 构造方法：一路到底，把根节点和它的所有左节点放到栈中
• 调用 next() 方法：弹出栈顶的节点；
• 如果它有右子树，则把右子树的根节点和右子树的所有左节点放到栈中。

cpp

class BSTIterator {
    std::stack<TreeNode *>stack;
    
    void leftmostInOrder(TreeNode *root){
        while (root != NULL){
            stack.push(root);
            root = root->left;
        }
    }
    
public:
    BSTIterator(TreeNode* root) {
        leftmostInOrder(root);
    }

    int next() {
        TreeNode *pop = stack.top(); stack.pop();
        if (pop->right != NULL){
            leftmostInOrder(pop->right);
        }
        return pop->val;
    }

    bool hasNext() {
        return stack.size() != 0;
    }
};

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

类似题目