1. 首先我们定义一个二叉树的结构体

1 struct TreeNode {2     int val;3     TreeNode *left;4     TreeNode *right;5     TreeNode(int x) : val(x), left(NULL), right(NULL) {}6 };

View Code

       对于二叉树的递归遍历比较简单，再次我就不详细介绍。下面主要介绍二叉树的先序、中序、后序三种非递归遍历。

• 先序非递归遍历  
  
  

   1 vector<int> preorderTraversal(TreeNode *root){ 2     vector<int> result; 3     stack<const TreeNode*> S; 4     if(root) S.push(root); 5     while (!S.empty()) 6     { 7         const TreeNode *cur = S.top(); 8         S.pop(); 9         result.push_back(cur->val);10         if(cur->right) S.push(cur->right);11         if(cur->left) S.push(cur->left);12     }13     return result;14 }

  View Code

• 中序非递归遍历
  在访问每个节点之前，一定先访问他的左节点(如果存在)。
  
  

   1 vector<int> inorderTraversal(TreeNode *root) { 2     vector<int> res; 3     stack<TreeNode*> s; 4     TreeNode *cur = root; 5     while(!s.empty()||cur){ 6         while (cur) 7         { 8             s.push(cur); 9             cur = cur->left;10         }11         res.push_back(s.top()->val);12         cur = cur->right;13         s.pop();14     }15     return res;16 }

  View Code
  
• 后序非递归遍历
  后序的遍历时在访问每个节点时，保证前一个访问的节点是这个节点的右节点
  
  

   1 vector<int> postorderTraversal(TreeNode *root){ 2         //cur记录当前节点，pre记录前一个结点 3         TreeNode *cur=root,*pre;  4         vector<int> res; 5         stack<TreeNode *> s; 6         while (!s.empty()||cur) 7         { 8             while(cur){ 9                 s.push(cur);10                 cur = cur->left;11             }12             pre = nullptr; 13             while(!s.empty()){14                 if(pre==s.top()->right){15                     res.push_back(s.top()->val);16                     pre = s.top(); 17                     s.pop();18                 }else19                 {20                     cur = s.top()->right;21                     break;22                 }23             }24         }25         return res;26     }

  View Code

   

   

二叉树的非递归遍历