Title Description:
Give you the root node of a binary tree, root, and return its node values Traverse the tree in bottom-up hierarchical order. (i.e., traverse from the leaf node level to the root node level, left to right, layer by layer)
Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]Thought Analysis:
This question is mainly a hierarchical traversal of a binary tree. Hierarchical traversal of a binary tree can be simulated using a queue, out of a queue at the same time the node child nodes are all added to the queue.
But he asked for reverse order input, so there are two ways to do it: 1. Use the header insertion method for insertion. 2. After insertion, just use the reverse order traversal once.
Focus on remembering the general logic of hierarchical traversal:Determine the number of nodes traversed out of the queue at one time by recording the length of the current queue (number of nodes in a layer)
Implementation of the head-interpolation method
res = append([][]int{tem},res... ) tem is []int{}
res... The role of res is to expand a slice, res is a two-dimensional slice, after the expansion of each element is a one-dimensional slice, and then append the first parameter is the target slice, the second element will be added to the first parameter after. Thus realizing the role of header insertion.
Click to view code
func levelOrderBottom(root *TreeNode) [][]int {
res,line:=[][]int{},[]*TreeNode{}
if root==nil {
return [][]int{}
}
line = append(line, root)
for len(line)>0 {
levelSize,tem := len(line),[]int{}
for i := 0; i < levelSize; i++ {
node := line[0]
line = line[1:]
if node != nil {
tem = append(tem, )
}
if != nil {
line = append(line, )
}
if != nil {
line = append(line, )
}
}
//Double-ended queues are good for scenarios where rollover is not possible，Direct use of header insertion
//res = append([][]int{tem},res... )
res = append(res, tem)
}
// Final inversion of hierarchy results
for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
res[i], res[j] = res[j], res[i]
}
return res
}