leet102.二叉树的层序遍历

题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内

• -1000 <= Node.val <= 1000

---

思路一

队列的先入先出天然适配树的层次遍历，

1. 从队列里面取一个元素出来，遍历它
2. 然后依次将它的左孩子和右孩子（如有）入队，这样左右孩子就在一层了
3. 下次遍历到左右孩子的时候，又会把孩子的孩子放到一层
4. 这样就做到了层次遍历

// 循环
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    if (!root) return ans;
 
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        vector<int> vals;
        // 小技巧：排空当前层，q若非空，肯定是上一层留下来的，
        // 因为遍历过程中有元素入队，所以先记录当前size，只遍历属于当前层的节点
        for (int n = q.size(); n--;) {
            auto p = q.front();
            q.pop();
            vals.push_back(p->val);
            if (p->left) q.push(p->left);
            if (p->right) q.push(p->right);
        }
        ans.push_back(std::move(vals));
    }
    return ans;
}

思路二

二叉树天然适配递归。

vector<vector<int>> levelOrder0(TreeNode* root) {
    vector<vector<int>> ans;
    // lambda静态捕获（since c++23）
    auto tranverse = [&](this auto&& tranverse, TreeNode* p, int depth) {
        if (!p) return;
        if (ans.size() <= depth) {
            ans.push_back(vector<int>());
        }
        ans[depth].push_back(p->val);
        tranverse(p->left, depth + 1);
        tranverse(p->right, depth + 1);
    };
    tranverse(root, 0);
    return ans;
}

这里是要返回一层一层的结果，如果只要按层次遍历依次输出（即所有元素铺开，只要一维 vector），则选用队列做更方便。

while (!q.empty()) {
	auto p = q.front();
	q.pop();
	ans.push_back(p->val);
	if (p->left) q.push(p->left);
	if (p->right) q.push(p->right);
}

---

see alse 二叉树的层次遍历