107.二叉树的层序遍历 II

【LetMeFly】107.二叉树的层序遍历 II：正常遍历后翻转

力扣题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

方法一：优先队列

与之前方法不同，这次决定不使用pair<TreeNode*, int>，而是直接使用TreeNode*入队。

看不懂的可以先看之前这篇博客：https://letmefly.blog.csdn.net/article/details/125584554

那么，没有了int类型的层数，怎么判断哪些节点是属于同一层的呢？

其实也很简单，我们在队列不空的时候，记录下来队列中一共由多少个元素，这些元素的个数就是当前最后一层的节点的个数。

然后，我们用一个循环，把这些元素全都添加到答案的同一层中（同时把子节点入队）即可。

• 时间复杂度$O(N)$，其中$N$是节点个数。
• 空间复杂度$O(N2)$，其中$N2$是节点最多的一层的节点数。

AC代码

C++

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        if (root)
            q.push(root);
        int layer = -1;
        while (q.size()) {
            ans.push_back({});
            layer++;
            int thisLayerNum = q.size();
            while (thisLayerNum--) {
                TreeNode* thisNode = q.front();
                q.pop();
                ans[layer].push_back(thisNode->val);
                if (thisNode->left)
                    q.push(thisNode->left);
                if (thisNode->right)
                    q.push(thisNode->right);
            }
        }
        reverse(ans.begin(), ans.end());  // 注意，这里是本题要求从最后一层开始遍历，所以reverse了以下。正常情况下的层次遍历是不需要reverse的
        return ans;
    }
};

Python

# from typing import List, Optional

# # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        q = []
        if root:
            q.append(root)
        while q:
            ans.append([])
            for _ in range(len(q)):
                thisNode = q[0]
                q = q[1:]
                ans[-1].append(thisNode.val)
                if thisNode.left:
                    q.append(thisNode.left)
                if thisNode.right:
                    q.append(thisNode.right)
        ans.reverse()
        return ans

其实Python的队列可以使用collections.deque。

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/125610699