開始的想法是先將葉子節點放入到一個vector中，然后依次next

下面的解法類似，但是只有在Next操作時才尋找下一個葉子節點

template <typename T> class Iterator {public:Iterator(T *root){if(root == NULL) return;st.push(root);probe();}bool hasNext() { return (st.size() > 0); }T *next(){T *node = st.top();st.pop();if(!st.empty())probe();return node;}private:stack<T *> st;bool leaf(T *node){return (node->leftChild() == NULL && node->rightChild() == NULL);}void probe(){T *now = st.top();while(!leaf(now)) {st.pop();if(now->rightChild())st.push(now->rightChild());if(now->leftChild())st.push(now->leftChild());now = st.top();}} };

不用空間的方法是，記錄上一次迭代到的葉子節點curr, 下一個葉子節點必須是經過curr的下一個葉子節點

struct NODE {int nVal;NODE* pLft;NODE* pRgt;NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL){} };void _inner_get_next(NODE* pNode, NODE* pIter, bool& bFlag, NODE*& pNext) {if (NULL == pNode) return;_inner_get_next(pNode->pLft, pIter, bFlag, pNext);if (NULL != pNext) return;if (bFlag && NULL == pNode->pLft && NULL == pNode->pRgt){pNext = pNode;return;}if (pIter == pNode) bFlag = true;_inner_get_next(pNode->pRgt, pIter, bFlag, pNext); }NODE* GetNext(NODE* pRoot, NODE* pIter) {if (NULL == pRoot || NULL == pIter)return NULL;NODE* pNext = NULL;bool bFlag = false;_inner_get_next(pRoot, pIter, bFlag, pNext);return pNext; }

總結

以上是生活随笔為你收集整理的二叉树叶子节点迭代器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。