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

Answer:

For this problem, we can first look at the corresponding schematic diagram of subsequent traversal, the picture is from the official problem solution.

The subsequent iteration of the final output sequence is as shown in the figure 1-2-3-4-5. All we need to do is actually use a stack to do this.

  1. From the picture, you can see that the order of the output nodes is 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 {TreeNode} root
 * @return {number[]}* /
var postorderTraversal = function (root) {
  let result = []; // Save the result.
  let stack = []; // Use the stack for traversal and output results.
  root && stack.push(root); // The list is traversed only when it has a value.

  // Iterate until the stack is empty
  while (stack.length) {
    // A node is popped from the stack one at a time, since the stack is pushed from top to bottom and left to right.
    // The unstack sequence becomes top to bottom and right to left.
    const node = stack.pop();

    // Because the final output is from bottom to top, left to right.
    // Insert the popup node to the front of the array each time, which guarantees the order of the final output.
    result.unshift(node.val);

    // The child nodes are pushed left to right to ensure the output order is right to left.
    node.left && stack.push(node.left);
    node.right && stack.push(node.right);
  }

  return result;
};
Copy the code