二叉树的前中后层序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

前序遍历

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

// 递归版
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
  let res = [];
  if(root === null) return res;
  res.push(root.val);
  res = res.concat(preorderTraversal(root.left));
  res = res.concat(preorderTraversal(root.right));
  return res;
};
// 迭代版
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
  let stack = [];
  let res = [];
  if(root === null) return res;
  stack.push(root);
  while(stack.length > 0) {
    let top = stack.pop();
    res.push(top.val);
    if(top.right) {
      stack.push(top.right);
    }
    if(top.left) {
      stack.push(top.left);
    }
  }
  return res;
};

Leetcode时间(后提交的为递归版本)

中序遍历

https://leetcode-cn.com/problems/binary-tree-inorder-traversal

// 递归
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  let res = [];
  if(root === null) return res;
  res = res.concat(inorderTraversal(root.left));
  res.push(root.val);
  res = res.concat(inorderTraversal(root.right))
  return res;
};
// 迭代
var inorderTraversal = function(root) {
  let stack = [];
  let res = [];
  while(root) {
    stack.push(root);
    root = root.left;
  }
  while(stack.length > 0) {
    let top = stack.pop();
    res.push(top.val);
    let right = top.right;
    while(right) {
      stack.push(right.left);
      right = right.left;
    }
  }
  return res;
}

Leetcode时间(后提交的为递归版本)

后序遍历

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

// 递归
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {  
  let res = [];
  if(root === null) return res;
  res = res.concat(postorderTraversal(root.left));
  res = res.concat(postorderTraversal(root.right));
  res.push(root.val);
  return res;
};

层次遍历

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

// 递归(常规)
// 如果想把每一层区分出来，则需要再while循环中加入一个 let q_size = q.length;
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var levelOrder = function(root) {
  let queue = [];
  let res = [];
  queue.push(root);
  while(queue.length > 0) {
    let front = queue.shift();
    res.push(front.val);
    if(front.left) queue.push(front.left);
    if(front.right) queue.push(front.right);
  }
  return res;
};