Original link: leetcode-cn.com/problems/n-…

Answer:

  1. The output nodes are traversed sequentially from bottom to top and left to right.
  2. We can iterate using a stack, with each loop pushing elements from top to bottom and left to right.
  3. Each time through the loop, the order of the elements out of the stack is top to bottom and right to left.
  4. But in this case, the stack elements are printed in the opposite order to the desired result order.
  5. The solution is to insert the output into the head of the result array so that the final output is ordered from bottom to top and left to right.
/ * * *@param {Node} root
 * @return {number[]}* /
var postorder = function (root) {
  let result = []; // Save the result
  let stack = []; // Use stack traversal
  root && stack.push(root); // Start traversal only when the binary tree exists

  // Traverses the binary tree until the stack is empty, i.e. traverses all nodes
  while (stack.length) {
    // Pops elements from the stack from top to bottom and from right to left
    const node = stack.pop();

    // Inserts the node's value to the front of the result array
    // Ensure that the output order is bottom to top and left to right
    result.unshift(node.val);

    // The child nodes are pushed from left to right
    if (node.children) {
      for (const child ofnode.children) { stack.push(child); }}}return result;
};
Copy the code