广度优先算法

层序遍历

经典迭代code

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> temp; // 缓冲器，用来保存从输入获取的节点
        vector<vector<int>> result; //最终输出的结果，用一个二维数组保存
        if (root != nullptr) //如果不为空则压入缓冲器，空则什么都不做，之后只要判断缓冲器是否为空
            temp.push(root);
        while (!temp.empty()) //开始循环更新缓冲器和结果数组
        {
            int size = temp.size(); //记录当前层的大小。保护后面压入的下一层数据不被这一层遍历
            vector<int> vec; //记录当前层的元素
            for (int i = 0; i < size;i++) //开始遍历当前层元素
            {
                TreeNode *cur = temp.front(); //获取缓冲器第一个元素
                temp.pop(); // 把这个元素弹出
                vec.push_back(cur->val); //把这个元素压入结果中
                if(cur->left)  // 如果左右有值，那么把值压入缓冲器，因为size变量的保护，本层不会破坏下一层的数据
                    temp.push(cur->left);
                if(cur->right)
                    temp.push(cur->right);
            }
            result.push_back(vec); //把这一层数据压入输出数组
        }
            //    reverse(result.begin(), result.end()); // 对顺序的树进行一个层级倒序
        return result; // 输出结果
    }
};