树的非递归遍历

1. 中根遍历

思路：

一直遍历左子树 p = p->left;

直到p为空。此时訪问栈顶元素，栈顶元素出栈。開始遍历右子树p = p->right;

遍历右子树的左子树

出栈时訪问

/** 1. Definition for a binary tree node. 2. struct TreeNode { 3.     int val; 4.     TreeNode *left; 5.     TreeNode *right; 6.     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 7. };*/class Solution {public:    vector
      
        inorderTraversal(TreeNode* root) {        vector
       
         ret;        if(root == NULL){            return ret;        }                stack
        
          ss;        TreeNode* p = root;        while(ss.empty()==false || p!=NULL){            if(p != NULL){                ss.push(p);                p = p->left;            }            else{                p = ss.top();                ss.pop();                ret.push_back(p->val);                p = p->right;            }        }        return ret;    }};
        
       
      

2. 先根遍历

与中根思路一样。仅仅是在入栈即訪问该节点

class Solution {public:    vector
      
        preorderTraversal(TreeNode* root) {        vector
       
         ret;        if(root == NULL){            return ret;        }        stack
        
          ss;        TreeNode * p = root;        while(ss.size() != 0 || p!=NULL){            if(p != NULL){                ss.push(p);                ret.push_back(p->val);                p = p->left;            }            else {                p = ss.top();                ss.pop();                p = p->right;            }        }        return ret;    }};
        
       
      

还有一种思路：

先把根压入栈，出栈时才訪问。

依照右左顺序把两个孩子压栈

class Solution {public:    vector
      
        preorderTraversal(TreeNode* root) {        vector
       
         ret;        if(root == NULL){            return ret;        }        stack
        
          ss;        ss.push(root);        while(ss.empty()==false){            TreeNode *p = ss.top();            ss.pop();            ret.push_back(p->val);            if(p->right != NULL){                ss.push(p->right);            }            if(p->left != NULL){                ss.push(p->left);            }        }        return ret;    }};
        
       
      

比較推荐另外一种，仅仅是第一种与树的中根遍历基本同样除了訪问位置。便于记忆。

3. 后根遍历

採用上述中根和先根统一的思路。前两者都须要訪问完左子树（左回），即能够pop当前节点。再訪问右子树

不同于上述两者，后根须要訪问完右子树才干pop当前节点(右回)，因此新定义了一个标记，開始訪问右子树时标记该节点。

当p为空，且栈顶元素被标记才訪问栈顶元素。

class Solution {public:    vector
      
        postorderTraversal(TreeNode* root) {        vector
       
         ret;        if(root == NULL){            return ret;        }        stack
        
          ss;        unordered_map
         
           mymap;  //here        TreeNode *p = root;        while(ss.empty()==false || p!=NULL){            if(p != NULL){                ss.push(p);                mymap[p] = false;//here                p = p->left;            }            else{                if(mymap[ss.top()] == false){                    p = ss.top()->right;                    mymap[ss.top()] = true;                }                else{                    //visit ss.top();                    ret.push_back(ss.top()->val);                    ss.pop();                }            }        }        return ret;    }};