LeetCode 题解：144. 二叉树的前序遍历，使用栈，JavaScript，详细注释

 关注

发布于: 2020 年 10 月 11 日

LeetCode题解：144. 二叉树的前序遍历，使用栈，JavaScript，详细注释

原题链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
﻿
解题思路：
﻿
对于该题，我们可以首先看前序遍历对应的示意图，图片来自官方题解。
﻿
﻿
前序遍历最后的输出顺序，就是按照图中的1-2-3-4-5。我们需要做的，其实是如何使用一个栈来实现这个过程。
﻿
从图片中，可以看到输出节点的顺序是由浅至深，从左到右。
每次循环时，将栈顶元素弹出1个，之后将其子元素入栈，保证了遍历由浅至深的顺序。
为了保证从右向左的顺序，我们必须将右节点先入栈，这样就保证了出栈时左节点优先，因此保证了遍历顺序。
﻿
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
  let result = []; // 保存结果
  let stack = []; // 使用栈遍历
  // 先将根节点入栈，开始遍历
  root && stack.push(root);
  // 不断弹出栈内元素，直至栈为空，此时所有节点都进行过入栈和出栈操作，即遍历了所有元素。
  while (stack.length) {
    // 将栈顶元素弹出，同时存储其值
    const node = stack.pop();
    result.push(node.val);
    // 入栈子节点，因此每次循环出栈的都是其子节点，保证了由浅至深的遍历顺序。
    // 先入栈右节点，后入栈左节点，保证出栈时先左后右，保证了从左向右的遍历顺序。
    node.right && stack.push(node.right);
    node.left && stack.push(node.left);
  }
  return result;
};
﻿