“This is the 22nd day of my participation in the First Challenge 2022. For details: First Challenge 2022”

The title

Give you the root node of the binary tree, root, and return a bottom-up traversal of its node values. (that is, from the layer where the leaf node is located to the layer where the root node is located, layer by layer from left to right)

Example 1:

Input: root = [3,9,20, null, null, 15, 7] output: [[15, 7], [9], [3]]Copy the code

Example 2:

Input: root = [1]Copy the code

Example 3:

Input: root = [] Output: []Copy the code

Tip:

The number of nodes in the tree is in the range [0, 2000] -1000 <= node. val <= 1000Copy the code

Source: LeetCode leetcode-cn.com/problems/bi…

Their thinking

Recursively: Starting with the root node, place the value of each node in the KTH array of the two-dimensional array, or insert an empty array if the two-dimensional array does not have the KTH array. K also represents the layer where the node resides. We recursively put the left and right children into the k + 1 array.

Then, through the double pointer, the recursive two-dimensional array is flipped to get the final result. The acquisition process is shown in the figure below:

Code implementation


var levelOrderBottom = function(root) {
    const ans = []

    // sequence traversal binary tree
    getResult(root, 0, ans)
    reverse(ans)

    return ans
};

var reverse = function(arr) {
    // Invert the array with a double pointer
    for (let i = 0, j = arr.length - 1; i < j; i++, j--) {
        // Swap the I and JTH arrays
        [arr[i], arr[j]] = [arr[j], arr[i]]
    }
}

/** * puts the value of root in the KTH array of ans, starting from 0 */
var getResult = function(root, k, ans) {
    // If root is empty, no action is required
    if(! root)return

    // If ans[k] does not exist, add an empty array to ans first
    if (k === ans.length) ans.push([])
    
    // Insert the root value at the end of the KTH array
    ans[k].push(root.val)
    
    // Place the value of the left node of root in the k + 1 array
    getResult(root.left, k + 1, ans)
    
    // Place the value of the right node of root in the k + 1 array
    getResult(root.right, k + 1, ans)
}
Copy the code

If there are mistakes welcome to point out, welcome to discuss together!