LC-二叉树的前序遍历

发表于 2019-08-14 更新于 2020-03-21 分类于 LeetCode

题目描述

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

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

输出: [1,2,3]

代码实现

递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
  if (!root) {
    return [];
  }
  let result = [];
  function recursive(root) {
    result.push(root.val);
    root.left && recursive(root.left);
    root.right && recursive(root.right);
  }
  recursive(root);
  return result;
};

栈 + 迭代

在前序后序和中序遍历中，这个的迭代方法应该是最好写的了。

这里注意要运用栈的原理

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
  if (!root) return [];
  let result = [];
  let stack = [root];
  while (stack.length) {
    let node = stack.pop();
    result.push(node.val);
    node.right && stack.push(node.right);
    node.left && stack.push(node.left);
  }
  return result;
};

LC-从前序与中序遍历序列构造二叉树

发表于 2019-08-13 更新于 2020-03-22 分类于 LeetCode

题目描述

105. 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

1 2	前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

代码实现

DFS（递归）

这是参考的评论区的一个解法，感觉十分易懂。这里的判断条件就是 l > r 是否成立。

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function (preorder, inorder) {
  function dfs(l, r) {
    if (l > r) {
      return null;
    }
    let val = preorder.shift();
    let root = new TreeNode(val);
    let index = inorder.indexOf(val);

    root.left = dfs(l, index - 1);
    root.right = dfs(index + 1, r);

    return root;
  }
  return dfs(0, inorder.length - 1)
}

LC-二叉树的层次遍历

发表于 2019-08-12 更新于 2020-03-21 分类于 LeetCode

题目描述

二叉树的层次遍历

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

例如：给定二叉树: [3,9,20,null,null,15,7]

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

代码实现

BFS（队列 + 迭代）

原理就是 BFS 一层一层地遍历，借助队列实现。

这个题的一个小技巧就是 let len = queue.length; 这行代码锁住了当前 for 循环的次数

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  if (!root) return [];
  let result = [];
  let queue = [root];
  while (queue.length) {
    let temp = [];
    let len = queue.length;
    for(let i = 0; i < len; i ++) {
      let node = queue.shift();
      node.left && queue.push(node.left);
      node.right && queue.push(node.right);
      temp.push(node.val);
    }
    result.push(temp);
  }
  return result;
};

DFS（递归）

根据 result 的长度和 depth 比较，如果 result.length === depth，就创建一个空的数组。

这里的 root.left && dfs(root.left, depth+1); 和 root.right && dfs(root.right, depth+1); 利用了 JavaScript 中 && 运算符的原理。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
  if (!root) {
    return [];
  }
  let result = [];
  function recursive(root, depth) {
    if (depth === result.length) {
      result[depth] = [];
    }
    result[depth].push(root.val);
    root.left && recursive(root.left, depth + 1);
    root.right && recursive(root.right, depth + 1);
  }
  recursive(root, 0)
  return result;
};