Amazon : implement binary tree leaf iterator

Implement Iterator on Binary Tree that iterates through leaf nodes left to right

1. template <typename T>
   
2. class Iterator
   
3. {
   
4.         public:
   
5.         Iterator(T *root)
   
6.         {
   
7.                 if(root == NULL) return;
   
8.                 st.push(root);
   
9.                 probe();
   
10.         }
    
11.         bool hasNext() { return (st.size() > 0); }
    
12.         T *next()
    
13.         {
    
14.                 T *node = st.top();
    
15.                 st.pop();
    
16.                 if(!st.empty())
    
17.                         probe();
    
18.                 return node;
    
19.         }
    
20.         private:
    
21.         stack<T *> st;
    
22.         bool leaf(T *node)
    
23.         {
    
24.                 return (node->leftChild() == NULL && node->rightChild() == NULL);
    
25.         }
    
26.         void probe()
    
27.         {
    
28.                 T *now = st.top();
    
29.                 while(!leaf(now)) {
    
30.                         st.pop();
    
31.                         if(now->rightChild())
    
32.                                 st.push(now->rightChild());
    
33.                         if(now->leftChild())
    
34.                                 st.push(now->leftChild());
    
35.                         now = st.top();
    
36.                 }
    
37.         }
    
38. };

复制代码

类似java中iterator的实现，tree node类必须有leftChild和rightChild方法。传入root指针，iterate所有叶节点的指针

下面是我的函数版,不要额外空间但是时间复杂度更大,类似于STL里对二叉树的iterator方法:

1. 
   
2. struct NODE
   
3. {
   
4.         int nVal;
   
5.         NODE* pLft;
   
6.         NODE* pRgt;
   
7. 
   
8.         NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL)
   
9.         {}
   
10. };
    
11. 
    
12. void _inner_get_next(NODE* pNode, NODE* pIter, bool& bFlag, NODE*& pNext)
    
13. {
    
14.         if (NULL == pNode) return;
    
15.         _inner_get_next(pNode->pLft, pIter, bFlag, pNext);
    
16. 
    
17.         if (NULL != pNext) return;
    
18.         if (bFlag && NULL == pNode->pLft && NULL == pNode->pRgt)
    
19.         {
    
20.                 pNext = pNode;
    
21.                 return;
    
22.         }
    
23. 
    
24.         if (pIter == pNode) bFlag = true;
    
25. 
    
26.         _inner_get_next(pNode->pRgt, pIter, bFlag, pNext);
    
27. }
    
28. 
    
29. NODE* GetNext(NODE* pRoot, NODE* pIter)
    
30. {
    
31.         if (NULL == pRoot || NULL == pIter)
    
32.                 return NULL;
    
33. 
    
34.         NODE* pNext = NULL;
    
35.         bool bFlag = false;
    
36.         _inner_get_next(pRoot, pIter, bFlag, pNext);
    
37. 
    
38.         return pNext;
    
39. }
    

复制代码