leecode144---二叉树前序遍历

leecode144—二叉树前序遍历

• 递归（leecode94的中序遍历也是类似的）
• 迭代：在94题的迭代法稍微修改：每次在左边一直循环遍历之前把根节点结果取值，然后借助栈返回上一个节点位置直接遍历右节点即可（中序遍历是左边遍历完就直接返回上一个节点位置，再取根节点结果，再遍历右节点）

/**
 * 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) {
  let result = []
  preorderF(result,root)
  return result
};
function preorderF(result,root) {
  //判断空结点
  if (root === null){return}
  //root
  result.push(root.val)
  //left
  preorderF(result,root.left)
  //right
  preorderF(result,root.right)
}


//迭代解法
var preorderTraversal = function(root) {
  const res = [];
  const stk = [];
  while (root || stk.length) {
    while (root) {
      res.push(root.val);//key
      stk.push(root);
      root = root.left;
    }
    root = stk.pop();
    root = root.right;
  }
  return res;
};

function TreeNode(val, left, right) {
  this.val = (val===undefined ? 0 : val)
  this.left = (left===undefined ? null : left)
  this.right = (right===undefined ? null : right)
}