subject

leetcode Original link

Give you the root node of the binary tree root , Returns its node value Bottom up sequence traversal . （ That is, from the layer where the leaf node is to the layer where the root node is , Traversal layer by layer from left to right ）

Example 1：

Input ：root = [3,9,20,null,null,15,7]
Output ：[[15,7],[9,20],[3]]

Example 2：
Input ：root = [1]
Output ：[[1]]

Example 3：
Input ：root = []
Output ：[]

Tips ：
The number of nodes in the tree is in the range [0, 2000] Inside
-1000 <= Node.val <= 1000

Ideas

• Think about this topic and this one 【leetcode】102. Sequence traversal of binary tree What is the difference between the results of topic traversal ？ In fact, it's the problem. Just flip the result array .
• The operation of flipping can be carried out when adding single-layer traversal results to the result array , That is, add... From the header of the array .

Code

/** * 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 []
    let queue = [root]
    let res = []
    while(queue.length){
    
        const len = queue.length
        let curLevel = []   // Store nodes of each layer 
        for(let i = 0 ; i < len ; i++){
    
            const curNode = queue.shift()
            curLevel.push(curNode.val)
            if(curNode.left) queue.push(curNode.left)
            if(curNode.right) queue.push(curNode.right)
        }
        res.unshift(curLevel)  // Store the traversal results of the current layer , Add from array header 
    }

    return res
};

Complexity

• Time complexity ：$O(n)$
• Spatial complexity ：$O(n)$

Pay attention to my special column , Update three times a day leetcode Answer key , Get stronger together ！