前序遍历

LeetCode 144

递归法

  1. class Solution {
  2. public:
  3.     void traverse(TreeNode* root, vector<int>& res) {
  4.         if(!root)
  5.             return;
  6.         res.push_back(root->val);
  7.         traverse(root->left, res);
  8.         traverse(root->right, res);
  9.     }
  10.     vector<int> preorderTraversal(TreeNode* root) {
  11.         vector<int> res;
  12.         traverse(root, res);
  13.         return res;
  14.     }
  15. };

迭代法

  1. class Solution {
  2. public:
  3.     vector<int> preorderTraversal(TreeNode* root) {
  4.         vector<int> ans;
  5.         stack<TreeNode*> s;
  6.         s.push(root);
  7.         while(!s.empty()) {
  8.             TreeNode *cur = s.top();
  9.             s.pop();
  10.             if(cur == NULL)
  11.                 continue;
  12.             ans.push_back(cur->val);
  13.             s.push(cur->right);
  14.             s.push(cur->left);
  15.         }
  16.         return ans;
  17.     }
  18. };

中序遍历

LeetCode 94

递归法

  1. class Solution {
  2. public:
  3.     void traverse(TreeNode* root, vector<int>& res) {
  4.         if(!root)
  5.             return;
  6.         traverse(root->left, res);
  7.         res.push_back(root->val);
  8.         traverse(root->right, res);
  9.     }
  10.     vector<int> inorderTraversal(TreeNode* root) {
  11.         vector<int> res;
  12.         traverse(root, res);
  13.         return res;
  14.     }
  15. };

迭代法

为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作，一个是处理：将元素放进result数组中，一个是访问：遍历节点。

分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，要先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

那么再看看中序遍历，中序遍历是左中右。
先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部。
再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode *cur = root;
        while(cur != NULL || !s.empty()) {
            if(cur != NULL) {
                s.push(cur);
                cur = cur->left;
            }
            else {
                cur = s.top();
                s.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

后序遍历

LeetCode 145

递归法

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

迭代法

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode *cur = root, *r = NULL;
        while(!s.empty() || cur) {
            if(cur) {
                s.push(cur);
                cur = cur->left;
            }
            else {
                cur = s.top();
                if(cur->right == NULL || cur->right == r) {
                    res.push_back(cur->val);
                    r = cur;
                    s.pop();
                    cur = NULL;
                }
                else {
                    cur = cur->right;
                }
            }
        }
        return res;
    }
};

层序遍历

迭代法

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root)
            return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            vector<int> list;
            int size = q.size();
            for(int i = 0; i < size; i++) {
                TreeNode *cur = q.front();
                q.pop();
                list.push_back(cur->val);
                if(cur->left)
                    q.push(cur->left);
                if(cur->right)
                    q.push(cur->right);
            }
            res.push(list);
        }
        return res;
    }
};

前中后序统一的迭代方法

垃圾回收机制中有一种算法叫做三色法：

  • 用白色表示尚未访问
  • 用灰色表示尚未完全访问子节点
  • 用黑色表示子节点已经完全访问

我们可以模仿类似的思路，使用双色标记法来统一三种遍历

  • 新节点为白色，已访问节点为灰色
  • 遇到白色节点，将其标记为灰色，然后将其左右节点，自身依次入栈。入栈顺序决定是哪种遍历。
  • 遇到灰色节点，则将该节点输出。
    const traversal = (root) => {
  const [white, gray] = [true, false]
const stk = [{ color: white, node: root }]
const res = []
while(stk.length) {
    const { color, node } = stk.pop()
  if(!node) continue
  if(color === white) {
      stk.push({ color: white, node: node.right })
    stk.push({ color: gray, node: node })
    stk.push({ color: white, node: node.left })
  }
  else res.push(node.val)
}
return res
}
    如要实现前序、后序遍历，也只需要调整左右子节点的入栈顺序即可，其他部分是无需做任何变化``