升序遍历一棵二叉搜索树
API：
-
BSTIterator(TreeNode* root)初始化 -
int next()将指针向右移动，然后返回指针处的数字 -
bool hasNext()如果向指针右侧遍历存在数字，则返回true否则返回false -
int peak()返回当前指针处的数字
/*** 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 {stack<TreeNode*>st;//用栈模拟递归void pushleft(TreeNode*p){//一路向左，全部进栈，最后栈顶是最小元素while(p){st.push(p);p=p->left;}}
public:BSTIterator(TreeNode* root) {pushleft(root);}int next() {auto p=st.top();st.pop();pushleft(p->right);//出栈后右孩子进栈return p->val;}bool hasNext() {return st.size();}int peak() {return st.top()->val;}};
leetcode 173
简单应用
给你 root1 和 root2 这两棵二叉搜索树
请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序
leetcode 1305
-
利用迭代器将树转化成链表
-
合并有序链表（类比归并排序）
class Solution {class BSTIterator {//…………};public:vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {BSTIterator s1(root1);BSTIterator s2(root2);vector<int>ans;while(s1.hasNext()&&s2.hasNext()){if(s1.peak()<s2.peak()){ans.push_back(s1.next());}else ans.push_back(s2.next());}while(s2.hasNext())ans.push_back(s2.next());while(s1.hasNext())ans.push_back(s1.next());return ans;}
};