算法训练营day13(11.11)

本节开始是关于二叉树内容，涉及到前序、中序、后序的递归和迭代遍历以及层序遍历。
递归遍历的思路非常简单，最原始的伪代码如下：

前序遍历
void preorder(TreeNode* root) {
    if(root != nullptr) {
        visit(root);
        preorder(root->left);
        preorder(root->right);
    }

中序和后序只是将visit函数放到左右子树中间或者之后即可。

而迭代的思路就比较复杂，我略过了统一迭代的代码。
对于前序，其迭代函数很简单(需要栈上先压入右子树，后压入左子树才能先处理左子树)：

void preorder(TreeNode* root) {
    if(root == nullptr) return;
    stack<int> stk;
    if(root != nullptr) stk.push(root);
    while(!stk.empty()) {
        TreeNode* cur = stk.top();
        stk.pop();
        visit(cur);
        if(cur->right) stk.push(cur->right);
        if(cur->left) stk.push(cur->left);
    }
}

而后序的处理只需要将前序迭代函数的左右子树压栈交换顺序，得到的结果中再重新reverse即可（因为得到的是"中右左"，而后序要求"左右中"）。
而中序遍历就比较麻烦，代码如下：

void inOrder(TreeNode* root) {
     if(root == nullptr) return;
     stack<int> stk;
      TreeNode *cur = root;
     if(cur!= nullptr) stk.push(cur);
     while(!stk.empty()) {
          if(cur->left != nullptr) {
              stk.push(cur);
              cur = cur->left;
          }
          else {
              cur = stk.top();
              stk.pop();
              visit(cur);
              cur = cur->right; 
          }
      }
}

层序遍历的递归算法比较简单明了，而迭代算法非常容易出错。
递归算法如下：

vector<vector<int>> levelOrder(TreeNode* root) {
    int depth = 0;
    vector<vector<int>> vec;
    levelOrder(root, vec, 0);
    return vec;
}
void levelOrder(TreeNode* root, vector<vector<int>>& vec, int depth) {
    if(root == nullptr) return;
    if(depth == vec.size()) vec.push_back(vector<int>());
    vec[depth].push_back(root->val);
    if(root->left) levelOrder(root->left, vec, depth + 1);
    if(root->right) levelOrder(root->right, vec, depth + 1);
}

层序遍历迭代算法如下：

void levelOrder(TreeNode* root) {
    queue<TreeNode*> que;
    if(root != nullptr) que.push(root);
    while(!que.empty()) {
        int size = que.size();
        for(int i = 0; i < size; i++) {
            TreeNode* cur = que.front();
            que.pop();
            visit(cur);
             if(que->left) que.push(que->left);
              if(que->right) que.push(que->right);
        }
     }
}

层序遍历的题目前9道都可以用递归方式很容易解决，而最后一道更适合迭代方式，题目太多不再一一列出答案，基本上套用前面的模板稍作变换即可。