LeetCode173--二叉搜索树迭代器

一、题目描述

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。调用 next() 将返回二叉搜索树中的下一个最小的数。

示例:

bst-tree

1
2
3
4
5
6
7
8
9
10
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false

提示:

  • next()hasNext() 操作的时间复杂度是,并使用内存,其中是树的高度。
  • 你可以假设 next() 调用总是有效的,也就是说,当调用 next() 时,BST 中至少存在一个下一个最小的数。

原题链接

二、分析

1.初步分析

  • 因为是二叉搜索树,首先想到的就是使用中序遍历,将结果依次存入数组中,这样调用 next() 将返回二叉搜索树中的下一个最小的数。

  • 这种想法满足了题目时间复杂度的要求,但是空间复杂度为为结点数。

2.优化

  • 调用next()将返回二叉搜索树中的下一个最小的数,其实我们只需要保证某个存储结构的头元素一定是最小的即可,对其他的暂时不管。

  • 因为空间复杂度要求是,再结合中序遍历的非递归实现,可以想到只需将最左侧结点入栈即可。

  • 当弹出一个结点后,如果它的右子树存在,则把右子树所有最左侧结点入栈,否则栈顶元素就是下一个最小元素。易知,在任意时刻栈中元素的个数,一定满足

三、解题代码

1.C++

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
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
private:
stack<TreeNode*> st;
public:
BSTIterator(TreeNode *root) {
//放最左侧节点
while(root){
st.push(root);
root = root->left;
}
}

/** @return whether we have a next smallest number */
bool hasNext() {
return !st.empty();
}

/** @return the next smallest number */
int next() {
TreeNode* node = st.top();
st.pop();
TreeNode* nowNode = node;
//将右子树的最左侧节点入栈,就是下一个最小节点
node = node->right;
while(node){
st.push(node);
node = node->left;
}
return nowNode->val;
}
};

2.Python

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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class BSTIterator:
"""
BST的最小结点就是最左侧的结点
BST的中序遍历结果是一个递增的序列, 借助栈来完成
"""
def __init__(self, root: TreeNode):
self.s = []
#将最左侧的结点入栈, 这样栈顶总是某一棵树的最小结点
while root != None:
self.s.append(root)
root = root.left

def next(self) -> int:
"""
@return the next smallest number
"""
smallest = self.s.pop()
#将smallest的右子树的最左侧结点入栈, 即稍大的结点
node = smallest.right
while node != None:
self.s.append(node)
node = node.left
return smallest.val

def hasNext(self) -> bool:
"""
@return whether we have a next smallest number
"""
return self.s != []

3.Go

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
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type BSTIterator struct {
s []*TreeNode
}


func Constructor(root *TreeNode) BSTIterator {
//将最左侧的结点入栈, 这样栈顶总是某一棵树的最小结点
iter := BSTIterator{s: []*TreeNode{}}
for root != nil {
iter.s = append(iter.s, root)
root = root.Left
}
return iter
}


/** @return the next smallest number */
func (this *BSTIterator) Next() int {
//取出栈顶结点
smallest := this.s[len(this.s) - 1]
this.s = this.s[:len(this.s) - 1]
//将smallest的右子树的最左侧结点入栈, 即稍大的结点
node := smallest.Right
for node != nil {
this.s = append(this.s, node)
node = node.Left
}
return smallest.Val
}


/** @return whether we have a next smallest number */
func (this *BSTIterator) HasNext() bool {
return len(this.s) != 0
}
------------- 本文结束 感谢您的阅读 -------------

本文标题:LeetCode173--二叉搜索树迭代器

文章作者:Perry

发布时间:2019年04月21日 - 13:25

最后更新:2019年09月20日 - 16:41

原始链接:https://perry96.com/archives/bf748b21.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%