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

Answer:

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

The final output order of the preceding traversal is 1-2-3-4-5 in the figure. 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 shallow to deep, from left to right.
  2. In each loop, the top element is popped up, and the sub-element is added to the stack to ensure the order of traversal from shallow to deep.
  3. In order to keep the order from right to left, we must push the right node onto the stack first, which ensures that the left node takes precedence on the exit of the stack, thus guaranteeing the traversal order.
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var preorderTraversal = function (root) {
  let result = []; // Save the result
  let stack = []; // Use stack traversal

  // Start traversal by pushing the root node onto the stack
  root && stack.push(root);

  // Continue to pop elements on the stack until the stack is empty, at which point all nodes have been on and off the stack, i.e. all elements have been traversed.
  while (stack.length) {
    // Pop the top element of the stack and store its value
    const node = stack.pop();
    result.push(node.val);

    // The child node is pushed into the stack, so the child node is looped out of the stack each time, ensuring the order of traversal from shallow to deep.
    // The right node is pushed first, and the left node is pushed later.
    node.right && stack.push(node.right);
    node.left && stack.push(node.left);
  }

  return result;
};
Copy the code