題目描述

題目分析

更加地覺得編程重要的不在于如何寫代碼，用什么具體的技巧，編碼本身只是一種將思維呈現的方式，但是如果思維是不清晰的，那么就算懂得再多的編碼的奇技淫巧也是沒有什么幫助的。相反，如果有一個清晰的思路，便能很輕松的寫出優雅的代碼。最近在看《編程大師訪談》，感覺很多大師都提到的一個思想：編程最重要的是數學而不是代碼本身。他們覺得本科教育完全不應該接觸計算機，而是應該學習數學、歷史等知識。我剛進大學的時候覺得學習高數、大學物理沒有絲毫意義，現在慢慢覺得那些知識對思維的訓練的重要程度比什么所謂的專業課重要的多。

大概花了二十分鐘做這道題，覺得最后的實現方式還是比較優美的。

其實題目要求的就是二叉搜索樹的中序遍歷，但是顯然不能使用遞歸的方式，因此一個棧是必須的，用一個指針指向當前返回的值。

通過對中序遍歷的模擬可以發現，任何時候這個指針都在指向一個子樹的最左側的節點。而下一個位置在其右子樹的最左側節點。如果沒有右子樹則返回棧中的下一個節點，該節點是當前節點最近的沒有訪問過的祖先。

總結一下：對于當前節點，我們不用訪問他的左子樹，因為它的左子樹要么為空要么已經訪問，我們會訪問他的右子樹，如果沒有右子樹則返回棧中的下一個節點。如果棧為空則返回空指針表示遍歷結束

問題在于我們什么時候入棧呢，正是在搜索一個子樹最左側節點的時候將其路徑上的節點全部入棧，記錄當前節點的所有祖先，最后再依次訪問。

class BSTIterator {
public:BSTIterator(TreeNode* root) {iter = find_min(root);}int next() {int ret = iter->val;if (iter->right != nullptr) {iter = find_min(iter->right);} else {if (!stk.empty()) {iter = stk.top();stk.pop();} else {iter = nullptr;}}return ret;}bool hasNext() {return iter != nullptr;}
private:stack<TreeNode *> stk; //保存根節點棧TreeNode *iter;TreeNode *find_min(TreeNode *root) {if (root == nullptr) return root;while (root->left != nullptr) {stk.push(root);root = root->left;}return root;}
};