二叉树的非递归遍历（二）

二叉树的非递归遍历

• 通过在遍历过一次的节点前面加入一个NULL指针，提示下一个节点遍历过一次了

  前序遍历

  class Solution {
  public:
      vector<int> preorderTraversal(TreeNode* root) {
          vector<int> result;
          stack<TreeNode*> st;
          if (root != NULL) st.push(root);
          while (!st.empty()) {
              TreeNode* node = st.top();
              if (node != NULL) {
                  st.pop();
                  if (node->right) st.push(node->right);  // 右
                  if (node->left) st.push(node->left);    // 左
                  st.push(node);                          // 中
                  st.push(NULL);
              } else {
                  st.pop();
                  node = st.top();
                  st.pop();
                  result.push_back(node->val);
              }
          }
          return result;
      }
  };

• 遍历过一次的节点第二次直接输出

  中序遍历

  class Solution {
  public:
      vector<int> inorderTraversal(TreeNode* root) {
          vector<int> result;
          stack<TreeNode*> st;
          if (root != NULL) st.push(root);
          while (!st.empty()) {
              TreeNode* node = st.top();
              if (node != NULL) {
                  st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                  if (node->right) st.push(node->right);  // 添加右节点（空节点不入栈）
  
                  st.push(node);                          // 添加中节点
                  st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。
  
                  if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）
              } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                  st.pop();           // 将空节点弹出
                  node = st.top();    // 重新取出栈中元素
                  st.pop();
                  result.push_back(node->val); // 加入到结果集
              }
          }
          return result;
      }
  };

• 针对没访问过的节点，先把他的左孩子入栈，再把NULL和自身入栈，再入栈右孩子

  后序遍历

  class Solution {
  public:
      vector<int> postorderTraversal(TreeNode* root) {
          vector<int> result;
          stack<TreeNode*> st;
          if (root != NULL) st.push(root);
          while (!st.empty()) {
              TreeNode* node = st.top();
              if (node != NULL) {
                  st.pop();
                  st.push(node);                          // 中
                  st.push(NULL);
  
                  if (node->right) st.push(node->right);  // 右
                  if (node->left) st.push(node->left);    // 左
  
              } else {
                  st.pop();
                  node = st.top();
                  st.pop();
                  result.push_back(node->val);
              }
          }
          return result;
      }
  };

• 针对没访问过的节点，先把自己和NULL入栈，再把右孩子入栈，再把左孩子入栈