(nice!!!)(LeetCode 面试经典 150 题) 173. 二叉搜索树迭代器 (栈)

思路：栈，时间复杂度0(n)。

C++版本：

/*** Definition for a binary tree node.* 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:stack<TreeNode*> st;TreeNode * tr; BSTIterator(TreeNode* root) {tr=root;}int next() {//每次先中序遍历trwhile(tr!=nullptr){st.push(tr);tr=tr->left;}// 确保当前是中序遍历的第一个节点tr=st.top();st.pop();int tmp=tr->val;//保留当前节点的右子树，便于下次接着进行中序遍历tr=tr->right;return tmp;}bool hasNext() {return tr!=nullptr || st.size()!=0 ;}
};/*** Your BSTIterator object will be instantiated and called as such:* BSTIterator* obj = new BSTIterator(root);* int param_1 = obj->next();* bool param_2 = obj->hasNext();*/

JAVA版本：

/*** 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 {TreeNode tr;Deque<TreeNode> st;public BSTIterator(TreeNode root) {tr=root;st=new LinkedList<TreeNode>();}public int next() {while(tr!=null){st.push(tr);tr=tr.left;}tr=st.pop();int tmp=tr.val;tr=tr.right;return tmp;}public boolean hasNext() {return tr!=null || !st.isEmpty() ;}
}/*** 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();*/

GO版本：

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
type BSTIterator struct {tr *TreeNodest []*TreeNode
}func Constructor(root *TreeNode) BSTIterator {return BSTIterator{tr:root}
}func (this *BSTIterator) Next() int {for this.tr!=nil {this.st=append(this.st,this.tr)this.tr=this.tr.Left}this.tr=this.st[len(this.st)-1];this.st=this.st[:len(this.st)-1]tmp:=this.tr.Valthis.tr=this.tr.Rightreturn tmp
}func (this *BSTIterator) HasNext() bool {return this.tr!=nil || len(this.st)>0
}/*** Your BSTIterator object will be instantiated and called as such:* obj := Constructor(root);* param_1 := obj.Next();* param_2 := obj.HasNext();*/