什么是二叉树前序遍历

前序遍历：1 2 4 5 7 8 3 6

前序遍历：根结点 —> 左子树 —> 右子树

前序遍历:
是二叉树遍历的一种， 也叫做 先根遍历 、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。
前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
若二叉树为空则结束返回，否则：
（1）访问根结点。
（2）前序遍历左子树。
（3）前序遍历右子树 。
需要注意的是：遍历左右子树时仍然采用前序遍历方法。
如上图所示二叉树
前序遍历结果：12457836

题目： 二叉树的前序遍历

给定一个二叉树，返回它的 前序 遍历。

示例 1：

输入: [1, null, 2, 3];
1
  \
  2
  /
3;

输出: [1, 2, 3];

答案

递归解题法： preOrder 函数将根节点 root 的val值加入数组，然后递归调用自身 获取left 跟 right 的 val值 , 递归止于 节点为null的时候。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
 const res = [];
 const preOrder = root => {
  if (root == null) return;
  res.push(root.val);
  preOrder(root.left);
  preOrder(root.right);
 };
 preOrder(root);
 return res;
};

const root = {
 val: 1,
 left: null,
 right: {
  val: 2,
  left: { val: 3, left: null, right: null },
  right: null,
 },
};

const res = preorderTraversal(root);

迭代解题法：
维护一个栈 stack，模拟递归的压栈出栈。
遍历 获取 val 值 ，把 right 节点 压入 stack 栈内 ， 把 left 节点 赋值 给 根节点 root
进入第二次遍历，判断栈 stack 是否有值，如果有 把 栈内的数据 pop 出来，赋值 给 root，并获取 root 的 val，
把 left 节点 赋值 给 root ，进入第三次遍历， 重复 第一次 遍历所做的事情

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
 const res = [];
 let stack = [];
 while (root) {
  res.push(root.val);
  if (root.right) stack.push(root.right);
  root = root.left;
 }

 while (stack.length) {
  root = stack.pop();
  res.push(root.val);
  if (root.right) stack.push(root.right);
  root = root.left;
  while (root) {
   res.push(root.val);
   if (root.right) stack.push(root.right);
   root = root.left;
  }
 }
 return res;
};

const root = {
 val: 1,
 left: null,
 right: {
  val: 2,
  left: { val: 3, left: null, right: null },
  right: null,
 },
};

const res = preorderTraversal(root);

---