“This is the 15th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Hope is a good thing, maybe the best of things. And no good thing ever dies.

preface

What is sequence traversal II

Sequence traversal II is consistent with the sequence traversal of binary tree. The data stored in each node is printed from top to bottom and left to right, and the Result vector can be flipped before the final return.

The data structure is shown below:

Compare the four traversal modes:

  • A → B → D → C
  • Middle order traversal: B → D → A → C
  • Subsequent traversal: D → B → C → A
  • Sequence traversal: A → B → C → D
  • Sequence traversal II: A → B → C → D

The title

Given a binary tree, 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)

For example, given a binary tree [3,9,20, NULL, NULL,15,7], 3 / \ 9 20 / \ 15 7 returns its bottom-up traversal as follows: [[15,7], [9,20], [3]]Copy the code

Add: leetcode-cn.com/problems/bi…

Ideas and Analysis

Use a variable to record the current layer

The subscript of the array is the current layer

If you are entering this layer for the first time,

Create an empty array

Otherwise, the node value is added to the array for that layer

Returns an array of

Reversing the returned array is the result

To sum up: each element of the queue records depth. An array of the same depth is returned, and then the array is reversed

The problem solving

/** * 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 == null) { return [] } let result = [] let queue = [root] while (queue.length) { let levelSize = queue.length; // Let curLevelResult = []; For (let I = 0; i < levelSize; i++) { const node = queue.shift(); curLevelResult.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } // Insert the array in reverse order (invert the result array) result.unshift(curLevelResult); } return result; };Copy the code

conclusion

If this article helped you, please like 👍 and follow ⭐️.

If there are any errors in this article, please correct them in the comments section 🙏🙏

Welcome to pay attention to my wechat public number, exchange technology together, wechat search 🔍 : “fifty years later”