{"id":2166,"date":"2016-09-05T15:22:28","date_gmt":"2016-09-05T07:22:28","guid":{"rendered":"http:\/\/boweihe.me\/?p=2166"},"modified":"2016-09-05T15:22:28","modified_gmt":"2016-09-05T07:22:28","slug":"leetcode-173-binary-search-tree-iterator","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2166","title":{"rendered":"LeetCode 173. Binary Search Tree Iterator"},"content":{"rendered":"<h3>\u601d\u8def<\/h3>\n<p>\u753b\u4e00\u4e2a\u7b80\u5355\u7684BST\uff0c\u7136\u540e\u53ef\u4ee5\u770b\u51fa\u6709\u4e09\u79cd\u60c5\u51b5<\/p>\n<ul>\n<li>\u5982\u679c\u5f53\u524d\u8282\u70b9\u6709\u53f3\u5b69\u5b50\uff0c\u90a3\u5c31\u5728\u53f3\u5b50\u6811\u91cc\u627e\u5230\u503c\u6700\u5c0f\u7684\u90a3\u4e2a\uff0c\u663e\u7136\u662f\u53f3\u5b50\u6811\u91cc\u6700\u5de6\u4e0b\u4fa7\u7684\u90a3\u4e2a\u8282\u70b9<\/li>\n<li>\u5982\u679c\u5f53\u524d\u8282\u70b9\u6ca1\u6709\u53f3\u5b69\u5b50\uff0c\u7531\u4e8e\u5de6\u5b50\u6811\u7684\u503c\u80af\u5b9a\u90fd\u6bd4\u5f53\u524d\u8282\u70b9\u7684\u503c\u5c0f\uff0c\u5de6\u53f3\u8981\u627e\u7236\u8282\u70b9\n<ul>\n<li>\u5982\u679c\u627e\u5230\u67d0\u4e2a\u7236\u8282\u70b9\u7684\u503c\u6bd4\u5f53\u524d\u8282\u70b9\u503c\u5927\uff0c\u90a3\u8fd9\u4e2a\u7236\u8282\u70b9\u5c31\u662f\u4e0b\u4e00\u8282\u70b9<\/li>\n<li>\u5426\u5219\uff0c\u5f53\u524d\u8282\u70b9\u5c31\u662f\u6700\u540e\u4e00\u4e2a\u8282\u70b9<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\u56e0\u6b64\uff0c\u9700\u8981\u4e00\u4e2a\u6808\u7ed3\u6784\u8bb0\u5f55\u5f53\u524d\u8282\u70b9\u7684\u7236\u4eb2\u4eec\uff08\u6709\u70b9\u50cf\u8c03\u7528\u6808\uff09\u3002<br \/>\n\u6d4b\u8bd5\u4f8b\uff1aNULL\u6839\u8282\u70b9\uff0c\u53ea\u6709\u4e00\u4e2a\u8282\u70b9\uff0c\u53ea\u6709\u5355\u4fa7\u6811<\/p>\n<h3>\u4ee3\u7801<\/h3>\n<pre class=\"lang:c++ decode:true \">\/**\n * Definition for binary tree\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}\n * };\n *\/\nclass BSTIterator {\nprivate:\n    stack&lt;TreeNode*&gt; callStack;\n    TreeNode* currNode;\n    TreeNode* rootNode;\npublic:\n    BSTIterator(TreeNode *root) {\n        currNode = NULL;\n        rootNode = root;\n    }\n    \/** @return whether we have a next smallest number *\/\n    bool hasNext() {\n        if(currNode == NULL){\n            currNode = rootNode;\n            while(currNode!=NULL &amp;&amp; currNode-&gt;left != NULL){\n                callStack.push(currNode);\n                currNode = currNode-&gt;left;\n            }\n            return currNode!=NULL;\n        }\n        if(currNode-&gt;right != NULL){\n            \/\/left-most node in right sub-tree\n            callStack.push(currNode);\n            currNode = currNode-&gt;right;\n            while(currNode-&gt;left != NULL){\n                callStack.push(currNode);\n                currNode = currNode-&gt;left;\n            }\n            return true;\n        } else {\n            \/\/look for first parent whos val is &gt; currNode-&gt;val. If not available, return false\n            int currVal = currNode-&gt;val;\n            while(!callStack.empty()){\n                TreeNode* parent = callStack.top();\n                callStack.pop();\n                if(parent-&gt;val &gt; currVal){\n                    currNode = parent;\n                    return true;\n                }\n            }\n            currNode = NULL;\n            return false;\n        }\n    }\n    \/** @return the next smallest number *\/\n    int next() {\n        if(currNode != NULL)\n            return currNode-&gt;val;\n        return INT_MIN;\n    }\n};\n\/**\n * Your BSTIterator will be called like this:\n * BSTIterator i = BSTIterator(root);\n * while (i.hasNext()) cout &lt;&lt; i.next();\n *\/<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u601d\u8def \u753b\u4e00\u4e2a\u7b80\u5355\u7684BST\uff0c\u7136\u540e\u53ef\u4ee5\u770b\u51fa\u6709\u4e09\u79cd\u60c5\u51b5 \u5982\u679c\u5f53\u524d\u8282\u70b9\u6709\u53f3\u5b69\u5b50\uff0c\u90a3\u5c31\u5728\u53f3\u5b50\u6811\u91cc\u627e\u5230\u503c\u6700\u5c0f\u7684\u90a3\u4e2a\uff0c\u663e\u7136\u662f\u53f3\u5b50\u6811\u91cc\u6700\u5de6\u4e0b\u4fa7\u7684\u90a3\u4e2a\u8282\u70b9 \u5982\u679c\u5f53\u524d\u8282\u70b9\u6ca1\u6709\u53f3\u5b69\u5b50\uff0c\u7531\u4e8e\u5de6\u5b50\u6811\u7684\u503c\u80af\u5b9a\u90fd\u6bd4\u5f53\u524d\u8282\u70b9\u7684\u503c\u5c0f\uff0c\u5de6\u53f3\u8981\u627e\u7236\u8282\u70b9 \u5982\u679c\u627e\u5230\u67d0\u4e2a\u7236\u8282\u70b9\u7684\u503c\u6bd4\u5f53\u524d\u8282\u70b9\u503c\u5927\uff0c\u90a3\u8fd9\u4e2a\u7236\u8282\u70b9\u5c31\u662f\u4e0b\u4e00\u8282\u70b9 \u5426\u5219\uff0c\u5f53\u524d\u8282\u70b9\u5c31\u662f\u6700\u540e\u4e00\u4e2a\u8282\u70b9 \u56e0\u6b64\uff0c\u9700\u8981\u4e00\u4e2a\u6808\u7ed3\u6784\u8bb0\u5f55\u5f53\u524d\u8282\u70b9\u7684\u7236\u4eb2\u4eec\uff08\u6709\u70b9\u50cf\u8c03\u7528\u6808\uff09\u3002 \u6d4b\u8bd5\u4f8b\uff1aNULL\u6839\u8282\u70b9\uff0c\u53ea\u6709\u4e00\u4e2a\u8282\u70b9\uff0c\u53ea\u6709\u5355\u4fa7\u6811 \u4ee3\u7801 \/** * 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&lt;TreeNode*&gt; callStack; TreeNode* currNode; TreeNode* rootNode; public: BSTIterator(TreeNode *root) { currNode = [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[27,66,133,164],"class_list":["post-2166","post","type-post","status-publish","format-standard","hentry","category-technical","tag-bst","tag-leetcode-oj","tag-133","tag-164"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2166","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2166"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2166\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2166"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2166"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2166"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}