一个模板：前序遍历、中序遍历、后序遍历

2020年3月7日 下午4:54

前序遍历

• Process代表是我们第一次遍历树各个节点的顺序，也就是前序遍历
• 第一次遍历树各个节点的顺序 = 前序遍历

  class Solution {
  public:
      vector<int> inorderTraversal(TreeNode* root) {
          if (root == NULL) return {} ;
          vector<int> ans;
          stack<TreeNode*> process;//记录路径点
  
          // 初始化：要初始化两个变量
          process.push(root); 
          ans.push_back(root->val); 
          TreeNode* cur = root->left;  
          // 循环不变式     
          while(1) {
              // 2.再反过头再检查！ 是否需要移动当前位置，如果找不到合适的位置，就结束程序！
              while (cur == NULL) {
                  if (process.empty()) return ans; 
                  cur = process.top()->right; 
                  // ans.push_back(process.top()->val);
                  process.pop();
              }
              // 1.先假装一切正常
              process.push(cur);
              ans.push_back(cur->val);
              cur = cur->left;
          }
          return ans;
      }
  };

中序遍历：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (root == NULL) return {} ;
        vector<int> ans;
        stack<TreeNode*> process;//记录路径点

        // 初始化：要初始化两个变量
        process.push(root); 
        TreeNode* cur = root->left;  
        // 循环不变式     
        while(1) {
            // 2.再反过头再检查！ 是否需要移动当前位置，如果找不到合适的位置，就结束程序！
            while (cur == NULL) {
                if (process.empty()) return ans; 
                cur = process.top()->right; 
                ans.push_back(process.top()->val);
                process.pop();
            }
            // 1.先假装一切正常
            process.push(cur);
            cur = cur->left;
        }
        return ans;
    }
};

后序遍历：

我最成功的地方在于分解了问题：

• 先可以正确的遍历
• 因为是后序遍历，和中序遍历对比，从定义出发，猜测：在中序的基础上，把top顶去掉，在找合适的时候插进去就行
• 这时，通过测试用例，先看看top是否拿出来了
• 最难是判断何时将top再放进去：这个标志得自己做，我这里使用的是高度！

1. 我不觉得从前序遍历 改到 后序遍历是一个好办法，其中太复杂了。主要目的还是锻炼一下自己的总结能力！
2. 【太复杂了，都无法用循环不等式证明！！！！，只能通过case一个个的试了】

   class Solution {
   public:
       vector<int> postorderTraversal(TreeNode* root) {
           if (root == NULL) return {} ;
           vector<int> ans;
           stack<TreeNode*> process;//记录路径点
           
           stack<TreeNode*> top; // 把顶点位置保存起来，再看什么时候插入
           stack<int> top_high; // 相同高度的时候插入
   
           // 初始化：要初始化两个变量
           process.push(root); 
           TreeNode* cur = root->left;  
           // 循环不变式     
           while(1) {
               // 2.再反过头再检查！ 是否需要移动当前位置，如果找不到合适的位置，就结束程序！
               while (cur == NULL) {
                   if (process.empty()) {
                       //  结束程序的时候，top中剩下的记得放入
                       while(!top.empty()) {
                           ans.push_back(top.top()->val);
                           top.pop();
                       }
                       return ans;
                   }
   
                   cur = process.top()->right; 
   
                   // 相同高度的时候插入top中的数据
                   while (!top_high.empty() && process.size() == top_high.top()) {
                       ans.push_back(top.top()->val);
                       top.pop();
                       top_high.pop();
                   }
                   
                   if (cur == NULL) {// cur == NULL时，我们可以直接放入ans中
                       ans.push_back(process.top()->val);
                       process.pop();
                   }
                   else {
                       top.push(process.top());// cur != NULL时，我们需要先暂存到top中
                       process.pop();
                       top_high.push(process.size());
                   } 
               }
               // 1.先假装一切正常
               process.push(cur);
               cur = cur->left;
           }
           
           return ans;
       }
   };