107. Binary Tree Level Order Traversal II
給定一個二元樹的根節點，返回其節點值的自底向上的層次遍歷。即從左到右，從葉子到根，一層層地遍歷。
範例：
輸入：root = [3,9,20,null,null,15,7] 輸出：[[15,7],[9,20],[3]]
這表明根據給定的二元樹，自底向上地逐層遍歷其節點值，結果如輸出所示。
Python
from collections import deque
from typing import Optional, List
# 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]]:
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result[::-1] # Reverse the result to get bottom-up order
16.89MB, 44ms
C++
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
vector<int> currentLevel;
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
currentLevel.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(currentLevel);
}
reverse(result.begin(), result.end());
return result;
}
};
13.78MB, 3ms
Javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val === undefined ? 0 : val)
* this.left = (left === undefined ? null : left)
* this.right = (right === undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrderBottom = function(root) {
if (!root) {
return [];
}
const result = [];
const queue = []; // Using an array to simulate a queue for BFS
queue.push(root);
while (queue.length > 0) {
const levelSize = queue.length;
const currentLevel = []; // Array to hold the current level's values
for (let i = 0; i < levelSize; i++) {
const node = queue.shift(); // Dequeue the front node
currentLevel.push(node.val);
if (node.left !== null) {
queue.push(node.left);
}
if (node.right !== null) {
queue.push(node.right);
}
}
result.push(currentLevel); // Add the current level's values to the result array
}
return result.reverse(); // Reverse the result to get bottom-up order
};
51.48MB, 69ms
