Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).
The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000
Solutions
Solution 1: BFS
We can use the BFS (Breadth-First Search) method to solve this problem. First, enqueue the root node, then continuously perform the following operations until the queue is empty:
Traverse all nodes in the current queue, store their values in a temporary array $t$, and then enqueue their child nodes.
Store the temporary array $t$ in the answer array.
Finally, return the reversed answer array.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 91011121314151617181920212223
# 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 = rightclassSolution:deflevelOrderBottom(self,root:Optional[TreeNode])->List[List[int]]:ans=[]ifrootisNone:returnansq=deque([root])whileq:t=[]for_inrange(len(q)):node=q.popleft()t.append(node.val)ifnode.left:q.append(node.left)ifnode.right:q.append(node.right)ans.append(t)returnans[::-1]
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funclevelOrderBottom(root*TreeNode)(ans[][]int){ifroot==nil{return}q:=[]*TreeNode{root}forlen(q)>0{t:=[]int{}forn:=len(q);n>0;n--{node:=q[0]q=q[1:]t=append(t,node.Val)ifnode.Left!=nil{q=append(q,node.Left)}ifnode.Right!=nil{q=append(q,node.Right)}}ans=append(ans,t)}fori,j:=0,len(ans)-1;i<j;i,j=i+1,j-1{ans[i],ans[j]=ans[j],ans[i]}return}