二叉树的前中后序遍历统一版本迭代写法(仅移动左中右顺序)

前序遍历

vector<int> preorderTraversal(TreeNode* root) {
    if(!root) return {};
    vector<int> result;
    stack<TreeNode*> stk;
    stk.push(root);
    while(!stk.empty()){
        TreeNode* node = stk.top();
        stk.pop();
        if(node){
            if(node -> right){
                stk.push(node -> right);
            }
            if(node -> left){
                stk.push(node -> left);
            } 
            stk.push(node);
            stk.push(nullptr);
        }else{
            result.push_back(stk.top()->val);
            stk.pop();
        }
    }
    return result;
}

中序遍历

vector<int> inorderTraversal(TreeNode* root) {
      if(!root) return {};
      vector<int> result;
      stack<TreeNode*> stk;
      stk.push(root);
      while(!stk.empty()){
          TreeNode* node = stk.top();
          stk.pop();
          if(node){
              if(node -> right){
                  stk.push(node -> right);
              }
              stk.push(node);
              stk.push(nullptr);
              if(node -> left){
                  stk.push(node -> left);
              } 
          }else{
              result.push_back(stk.top()->val);
              stk.pop();
          }
      }
      return result;
  }

后序遍历

vector<int> postorderTraversal(TreeNode* root) {
    if(!root) return {};
    vector<int> result;
    stack<TreeNode*> stk;
    stk.push(root);
    while(!stk.empty()){
        TreeNode* node = stk.top();
        stk.pop();
        if(node){
            stk.push(node);
            stk.push(nullptr);
            if(node -> right){
                stk.push(node -> right);
            }
            if(node -> left){
                stk.push(node -> left);
            } 
        }else{
            result.push_back(stk.top()->val);
            stk.pop();
        }
    }
    return result;
}