前序位置本身没有特别的性质（但我们们往往习惯将对前中后序位置不敏感的代码写在前序位置，所以很多题都是在前序位置写代码）
- 前序位置的代码执行是自顶向下的，因为前序位置是刚进入节点的时刻。因此前序位置只能得到当前节点的信息，不能得到子树的信息。
中序位置主要用在二叉搜索树（BST），二叉搜索树的中序遍历就相当于遍历有序数组
后序位置的代码执行是自底向上的，因为后序位置是即将离开节点的时刻
- 因此，后序位置既能得到当前节点的信息，还能获得左、右子树通过递归函数返回的数据
- 也就是说，如果题目和子树有关，那么大概率要给函数设置合理的定义和返回值，在后序位置写代码

1、递归

1.1 前序遍历

class Solution {
private:
    void preOrder(TreeNode* root, vector<int>& result)
    {
        result.push_back(root->val);
        if(root->left != nullptr)
            preOrder(root->left, result);
        if(root->right != nullptr)
            preOrder(root->right, result);
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root != nullptr)
            preOrder(root, result);
        return result;
    }
};

[简单] 144. 二叉树的前序遍历

1.2 中序遍历

class Solution {
    void inorder(TreeNode* root, vector<int>& result)
    {
        if(root->left)
            inorder(root->left, result);

        result.push_back(root->val);

        if(root->right)
            inorder(root->right, result);
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root)
            inorder(root, result);
        return result;
    }
};

1.3 后序遍历

class Solution {
    void postorder(TreeNode* root, vector<int>& result)
    {
        if(root->left != nullptr)
            postorder(root->left, result);
        if(root->right != nullptr)
            postorder(root->right, result);
        result.push_back(root->val);
    }
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;

        if(root != nullptr)
            postorder(root, result);

        return result;
    }
};

[简单] 145. 二叉树的后序遍历

2、迭代

★★★☆分别用递归和非递归方式实现二叉树先序、中序和后序遍历

2.1 前序遍历

前序遍历的输出顺序是 root, left, right ，按递归思路就是先访问根节点，再访问左子树，最后访问右子树。
因此，在迭代算法中，每访问到一个节点，就先输出这个节点的值（即存入 result 数组末尾），并将当前节点入栈，待遍历完左子树，再从栈顶访问根节点（并弹出），遍历右子树

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> nodeS;
        TreeNode* cur = root;
        while(cur != nullptr || !nodeS.empty())
        {
            while(cur != nullptr)                // 每访问一个节点
            {
                result.push_back(cur->val);        // 先输出当前节点的值
                nodeS.push(cur);                // 并将当前节点入栈
                cur = cur->left;                // 继续访问左子树
            }                                    
            //左子树遍历完毕

            cur = nodeS.top();        // 取出栈顶并弹出
            nodeS.pop();
            cur = cur->right;        // 访问右子树
        }
        return result;
    }
};

2.2 中序遍历

中序遍历的输出顺序是 left, root, right，按递归思路就是先访问左子树，再访问根节点，最后访问右子树。
因此，每访问到一个节点，先将其入栈，待遍历完左子树后，再从栈顶访问根节点，最后遍历右子树

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> nodeS;
        TreeNode* cur = root;
        while(cur != nullptr || !nodeS.empty())
        {
            while(cur != nullptr)    // 每访问一个节点
            {
                nodeS.push(cur);    // 将当前节点入栈（先不输出）
                cur = cur->left;    // 继续访问左子树
            }
            // 左子树遍历结束

            cur = nodeS.top();                // 取出栈顶并弹出
            nodeS.pop();
            result.push_back(cur->val);        // 输出当前元素
            cur = cur->right;                // 访问右子树
        }
        return result;
    }
};

2.3 后序遍历

后序遍历的输出顺序是 left, right, root
前序遍历的输出顺序是 root, left, right
将前序遍历的迭代方式做一下对称，即先访问根节点，再访问右子树，最后访问左子树，得到输出顺序 root, right, left

可以看到上面前序遍历的对称得到的输出和后序遍历刚好相反，因此将其逆序就是后序遍历的输出

class Solution {
public:
  vector<int> postorderTraversal(TreeNode* root) {
      vector<int> result;
      stack<TreeNode*> nodeS;
      TreeNode* cur = root;
      while(cur != nullptr || !nodeS.empty())
      {
          while(cur != nullptr)                // 每访问一个节点
          {
              result.push_back(cur->val);        // 先输出当前节点
              nodeS.push(cur);                // 并将当前节点入栈
              cur = cur->right;                // 继续访问右子树
          }
          // 右子树遍历完毕

          cur = nodeS.top();                    // 取出栈顶元素并弹出
          nodeS.pop();
          cur = cur->left;                    // 访问左子树
      }
      reverse(result.begin(), result.end());    // 将对称的前序遍历结果逆序，就是后序遍历的结果
      return result;
  }
};

3、迭代的通用简化解法

参考：颜色标记法-一种通用且简明的树遍历方法

可以使用两个栈 nodeS、visitedS 分别存储节点、这个节点是否被访问过（也可以使用一个栈，存储 pair<节点, 这个节点是否被访问过>）

以中序遍历为例，

初始将 root, false 分别压入nodeS、visitedS 栈
迭代，每次取两个栈的栈顶元素 node、visited，并弹出栈顶，直至栈为空
- 如果 node == nullptr，跳过，取下一个栈顶
- 否则，
  - 如果 visited == false，即是第一次访问这个节点 node，则：
    - 先将 node 的右子树节点、false 压入栈
    - 再将 node 节点、true 压入栈（表示 node 节点已访问过一次）
    - 最后将 node 的左子树节点、false 压入栈
  - 否则，是第二次访问这个节点 node，将节点的值输出

注：

中序遍历的输出顺序（即出栈顺序）是 左子树、根节点、右子树，因此入栈顺序应为 右子树、根节点、左子树
前序遍历的输出顺序（即出栈顺序）是 根节点、左子树、右子树，因此入栈顺序应位 右子树、左子树、根节点
后序遍历的输出顺序（即出栈顺序）是 左子树、右子树、根节点，因此入栈顺序应位 根节点、右子树、左子树

改变入栈顺序即可得到前、中、后序遍历

中序遍历代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;

        stack<TreeNode*> nodeS;        // 节点栈
        stack<bool> visitedS;        // 访问栈
        // 初始压入根节点
        nodeS.push(root);
        visitedS.push(false);
        while(!nodeS.empty())
        {
            // 取栈顶，并弹出
            TreeNode* node = nodeS.top();
            bool visited = visitedS.top();
            nodeS.pop();
            visitedS.pop();
            // 如果栈顶的节点 node 为空，则跳过；否则，
            if(node != nullptr)
            {
                // 如果节点 node 是第一次被访问
                if(visited == false)
                {
                    // 先将右子树压入栈中
                    nodeS.push(node->right);
                    visitedS.push(false);
                    // 再将 node 本身压入栈中
                    nodeS.push(node);
                    visitedS.push(true);
                    // 最后将左子树压入栈中
                    nodeS.push(node->left);
                    visitedS.push(false);
                }
                // 如果节点 node 是第二次被访问，则输出 node 的值
                else
                    result.push_back(node->val);
            }
        }

        return result;
    }
};

4、Morris 遍历

★★★★遍历二叉树的神级方法(Morris遍历)

CodeTop 企业题库

二叉树的前/中/后序/层序遍历