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

Answer:

144. Binary tree traversal is a binary tree traversal. 144. Binary tree preorder traversal, using stack, JavaScript, detailed comments.

  1. The order of the preceding traversal is top to bottom, left to right, and left to bottom first.
  2. The stack is used to traverse the elements, with each loop storing the value of the top element in the result.
  3. The child nodes of the current element are also traversed from right to left, which ensures that the order is top to bottom, left to right, and first left to bottom.
/ * * *@param {Node} root
 * @return {number[]}* /
var preorder = function (root) {
  let result = []; // Save the traversal result
  let stack = []; // Use stack traversal
  root && stack.push(root); // Stack the root node and start traversal

  // If the stack is empty, the traversal is complete.
  while (stack.length) {
    // Pops the top element of the stack, which is the result of the current iteration
    const node = stack.pop();
    result.push(node.val);

    // Continue traversal only if child nodes exist
    if (node.children) {
      // Each time a node is traversed, the children of the current node are pushed to ensure the traversal order from top to bottom.
      // The child nodes are pushed from right to left to ensure the order from left to right.
      // At the same time, the child node on the left is the first to be removed from the stack.
      for (let i = node.children.length - 1; i >= 0; i--) { stack.push(node.children[i]); }}}return result;
};
Copy the code