代码随想录算法训练营第十四天| 递归遍历 ● 迭代遍历 ● 统一迭代

递归遍历、层序遍历

递归遍历

思路：
忙，待补
特殊情况：

前序代码实现

void preTra(TreeNode* node, vector<int>& vec){
        if(node == nullptr) return;

        vec.push_back(node->val);
        preTra(node->left, vec);
        preTra(node->right, vec);
    }

中序代码实现

void inorderTra(TreeNode* node, vector<int>& vec){
        if(node == nullptr) return;


        inorderTra(node->left, vec);
        vec.push_back(node->val);
        inorderTra(node->right, vec);
    }

后序代码实现

void postTra(TreeNode* node, vector<int>& vec){
        if(node == nullptr) return;


        postTra(node->left, vec);
        postTra(node->right, vec);
        vec.push_back(node->val);
    }

迭代遍历 （层序遍历）

思路：
忙，待补
特殊情况：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> result;
        if(root != nullptr) que.push(root);
        
        while(!que.empty()){
            // 这里一定要使用固定大小size，不要使用que.size()
            //因为que.size是不断变化的，而本次while循环时只将当前层的元素访问
            int size = que.size();
            vector<int> vec;

            for(int i = 0; i < size; i++){
                //只将队列当前层的元素弹出访问，同时将其下一层的节点加入队列，。
                TreeNode* cur = que.front();
                que.pop();
                vec.push_back(cur->val);
                
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }

            result.push_back(vec);
        }

        return result;
    }
};