86. Binary Search Tree Iterator

发表于 更新于 阅读次数：

遍历二查找叉树

LintCode链接

题目描述

设计一个迭代器，该迭代器可以按照以下要求一棵二叉查找树

  • 遍历的顺序按照从小到大的排序规则
  • next与hasNext的时间复杂度平均为O(1)

样例

对于下面的二叉树，使用迭代器遍历将按照如下顺序遍历：[1, 6, 10, 11, 12]

1
2
3
4
5
   10
 /    \
1      11
 \       \
  6       12

思路

首先需要理解二叉查找树的概念：所有左节点的元素都比当前元素小，所有右节点的元素都比当前元素大。
遍历方式很简单，数据结构课程上都写过，唯一需要注意的是，题目定义的TreeNode没有存储parent变量，所以需要使用一个stack来存储当前的遍历层级，这样可以快速的找到父节点。内存复杂度为O(h)，h为树的高度，时间复杂为平均为O(1)

代码

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
class BSTIterator {
public:
    /*
    * @param root: The root of binary tree.
    */
    stack<TreeNode*> _node;
    BSTIterator(TreeNode * root) {
    	push(root);
    }
    
    void push(TreeNode *node)
    {
    	while (node)
    	{
    		_node.push(node);
    		node = node->left;
    	}
    }
    
    /*
    * @return: True if there has next node, or false
    */
    bool hasNext() {
    	// write your code here
    	return _node.empty() == false;
    }
    
    /*
    * @return: return next node
    */
    TreeNode * next() {
    	// write your code here
    	if (_node.empty())
    	{
    		return NULL;
    	}
    	TreeNode* ret = _node.top();
    	_node.pop();
    	push(ret->right);
    	return ret;
    }
};

后记

查了下资料，stl中的map使用类似思路，但是为了迭代器在插入元素与删除元素后不会失效，节点会存储parent，不适用辅助的stack变量，所以内存复杂度为O(1)，时间复杂度平均值也为O(1)，可以看到map迭代遍历的方式会有一个遍历找下一个节点的开销，开销最大为O(logN)，所以综合效率肯定没有顺序容器的快