给定一个二叉树，返回它的中序 遍历。

c plus

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  • 递归 ```cpp class Solution { public: vector res; vector inorderTraversal(TreeNode* root) {
    1.   helper(root);
    2.   return res;
    } void helper(TreeNode* root) {
    1.   if (root == NULL) return;
    2.   helper(root->left);
    3.   res.push_back(root->val);
    4.   helper(root->right);
    }

};

  2. - 迭代法
  4. 思路：每到一个节点 A，因为根的访问在中间，将 A 入栈。然后遍历左子树，接着访问 A，最后遍历右子树。<br />在访问完 A 后，A 就可以出栈了。因为 A 和其左子树都已经访问完成。
  5. ```cpp
  6. 栈s;
  7. p= root;
  8. while(p || s不空){
  9.     while(p){
  10.         p入栈;
  11.         p = p的左子树;
  12.     } //左子树入栈
  13.     p = s.top 出栈;
  14.     访问p;
  15.     p = p的右子树; //右子树入栈
  16. }
  1. class Solution {
  2. public:   
  3.     vector<int> inorderTraversal(TreeNode* root) {
  4.         vector<int> res;
  5.         if (!root) return res;
  6.         stack<TreeNode* >s;
  7.         TreeNode* cur = root;
  8.         while(cur || !s.empty()) {
  9.             while (cur) {         //先根--左 顺序入栈
  10.                 s.push(cur);
  11.                 cur = cur->left;
  12.             }
  13.             cur = s.top(); s.pop(); //左子树出栈，同时也是跟节点
  14.             res.push_back(cur->val);
  15.             cur = cur->right; //处理右子树
  16.         }
  17.         return res;
  18.     }
  19. };
  20. //前序遍历 根左右
  21. class Solution {
  22. public:
  23.     vector<int> preorderTraversal(TreeNode* root) {
  24.         vector<int> res;
  25.         stack<TreeNode *>s;
  26.         TreeNode *rt = root;
  27.         while (rt || s.size())
  28.         {
  29.             while (rt) {
  30.                 res.push_back(rt->val);//先把根节点存结果      
  31.                 s.push(rt->right);   //右节点入栈
  32.                 rt = rt->left;       //左节点
  33.             }
  34.             rt = s.top();s.pop();    //
  35.         }
  36.         return res;
  37.     }
  38. };

更好理解的模板

  • 中序遍历 左根右 ```cpp //中序遍历 class Solution { public: vector inorderTraversal(TreeNode* root) {
    1.   vector<int> res;
    2.   if (!root) return res;
    3.   stack<TreeNode* >s;
    4.   while(root || !s.empty()) {
    5.       if (root) {
    6.           s.push(root);
    7.           root = root->left;
    8.       }else { //说明到达栈顶了，树底。因为上面的root->left为空了。 
    9.           root = s.top(); s.pop();
    10.           res.push_back(root->val);  //出栈，处理结果
    11.           root = root->right;        //把右子树入栈
    12.       }
    13.   }
    14.   return res;
    } };

//前序遍历 只改变了一下处理结果时的位置 class Solution { public: vector preorderTraversal(TreeNode root) { vector res; stack<TreeNode >s; while(root || !s.empty()) { if (root) { res.push_back(root->val); //出栈，处理结果 s.push(root); root = root->left; }else { //说明到达栈顶了。因为上面的root->right为空了。 root = s.top(); s.pop(); root = root->right; //把右子树入栈 } } return res; } };

//后序遍历 左右根 class Solution { public: vector postorderTraversal(TreeNode root) { vector res; stack<TreeNode> s; TreeNode last = NULL; while (root || !s.empty()) { if (root) { s.push(root); root = root->left; } else { TreeNode cur = s.top(); if (cur->right && last != cur->right) { root = cur->right; //将右子树入栈 } else {
s.pop(); //如果右子树非空，则处理当前节点，并标记 res.push_back(cur->val); last = cur; //记录已经遍历过的几点，防止死循环。 } } } return res; } }; ```