二叉树的遍历

下面是二叉树的遍历，先序，中序和后序都采用了栈的方式，层序使用的是递归的方式，主要是leecode的要求，二叉树的遍历还是递归容易。
  1 #include <iostream>
  2 #include <vector>
  3 #include <stack>
  4 using std::stack;
  5 using std::vector;
  6 
  7 struct TreeNode{
  8     int val;
  9     TreeNode* leftNode;
 10     TreeNode* rightNode;
 11     TreeNode(int x) : val(x),leftNode(nullptr),rightNode(nullptr) {}
 12 };
 13 
 14 class Solution {
 15 public:
 16     vector<int> preOrderTraversal(TreeNode* root) {
 17         vector<int> res = {};
 18         stack<TreeNode*> s;
 19         if(root)  s.push(root);
 20         TreeNode* p;
 21         while(!s.empty())
 22         {
 23             p = s.top();
 24             res.push_back(p->val);
 25             s.pop();
 26             if(p->rightNode)  s.push(p->rightNode);
 27             if(p->leftNode) s.push(p->leftNode);  
 28         }
 29         return res;
 30     }
 31 
 32     vector<int> inOrderTraversal(TreeNode* root)
 33     {
 34         vector<int> res = {};
 35         stack<TreeNode*> s;
 36         TreeNode* p = root;
 37         while(!s.empty() || p)
 38         {
 39             if(p)
 40             {
 41                 s.push(p);
 42                 p= p->leftNode;
 43             }
 44             else
 45             {
 46                 p = s.top();
 47                 res.push_back(p->val);
 48                 s.pop();
 49                 p = p->rightNode;
 50             }
 51         }
 52         return res;
 53     }
 54 
 55     vector<int> postOrderTraversal(TreeNode* root)
 56     {
 57         vector<int> res = {};
 58         stack<TreeNode*> s;
 59         TreeNode* p = root; //being access
 60         TreeNode* q = nullptr; //previous access
 61 
 62         do{
 63             while(p)
 64             {
 65                 s.push(p);
 66                 p = p->leftNode;
 67             }
 68             q = nullptr;
 69             while(!s.empty())
 70             {
 71                 p = s.top();
 72                 s.pop();
 73                 if(p->rightNode == q)
 74                 {
 75                     res.push_back(p->val);
 76                     q = p;
 77                 }
 78                 else
 79                 {
 80                     s.push(p);
 81                     p = p->rightNode;
 82                     break;
 83                 }
 84             }
 85         }while(!s.empty());
 86         return res;
 87     }
 88 
 89     vector<vector<int>> levelOrderTraversal(TreeNode* root)
 90     {
 91         vector<vector<int>> res;
 92         if(!root) return res;
 93         levelOrderTraversalCore(root,1,res);
 94         return res;
 95     }
 96 private:
 97     void levelOrderTraversalCore(TreeNode* root,int level,vector<vector<int>>& res)
 98     {
 99         if(!root) return;
100         if(level > res.size()) 
101             res.push_back(vector<int>());
102         res[level-1].push_back(root->val);
103         levelOrderTraversalCore(root->leftNode,level+1,res);
104         levelOrderTraversalCore(root->rightNode,level+1,res);
105     }
106 };