放肆青春的博客
首页
前端
算法
网络
面试
技术
后端
运维
杂项
数据库
工具
网址
电脑
个人
文章
  • 分类
  • 标签
  • 归档
github (opens new window)
gitee (opens new window)

放肆青春

一个前端菜鸟的技术成长之路
首页
前端
算法
网络
面试
技术
后端
运维
杂项
数据库
工具
网址
电脑
个人
文章
  • 分类
  • 标签
  • 归档
github (opens new window)
gitee (opens new window)
  • 算法基础

    • 数据结构和算法
    • 算法blog
    • 算法基础
    • 算法思维
  • 算法汇总

    • 常见算法题
    • 穷举算法(枚举算法)
    • 递归
    • 二分法
    • 双指针

      • 双指针
      • 双指针算法题
      • 滑动窗口
      • 滑动窗口算法题
    • 回溯法

      • 回溯法
      • 回溯法算法题
    • 分治算法
    • 贪心算法

      • 贪心算法
      • 贪心算法题
    • 动态规划

      • 动态规划
      • 动态规划算法题
  • 排序算法

    • 排序算法
    • 1. 冒泡排序
    • 2. 选择排序
    • 3. 插入排序
    • 4. 希尔排序
    • 5. 归并排序
    • 6. 快速排序
    • 7. 堆排序
    • 8. 计数排序
    • 9. 桶排序
    • 10. 基数排序
  • 数据结构

    • 数组

      • 数组概览
      • 数组算法题
    • 字符串

      • 字符串概览
      • 字符串算法题
    • 树

      • 树概览
      • 树算法题
        • 树算法题
          • 二叉树的层序遍历【L102】
          • 二叉树的前序遍历【L144】
          • 二叉树的中序遍历【L94】
          • 二叉树的后序遍历【L145】
          • 二叉树的最大深度【L104】
          • 合并二叉树 【L617】
          • 二叉搜索树的第 k 大节点【O54】
          • 翻转二叉树 【L216】
    • 链表

      • 链表概览
      • 双向链表
      • 链表算法题
    • 队列

      • 队列概览
      • 队列算法题
    • 堆

      • 堆概览
      • 堆算法题
    • 散列表(哈希表)

      • 散列表(哈希表)概览
      • 散列表(哈希表)算法题
    • 栈

      • 栈概览
      • 栈算法题
    • 图

      • 图概览
      • 图算法题
  • algorithm
放肆青春
2021-09-07

树算法题

# 树算法题

# 二叉树的层序遍历【L102】

  1. 递归实现

广度优先搜索:有一个队列,维护当前深度变量,保证入队列的时候左子节点在右子节点前面

var levelOrder = function(root) {
  const res = [];
  function traversal(root, depth) {
    if (root !== null) {
      // 如果这一层级没有的情况下,初始化为空数组
      if (!res[depth]) res[depth] = [];
      res[depth].push(root.val);
      // 保证左子节点在右子节点前面就行,这样入队列的情况下也能保持左右顺序
      traversal(root.left, depth + 1);
      traversal(root.right, depth + 1);
    }
  }
  traversal(root, 0);
  return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  1. 迭代实现
var levelOrder = function(root) {
  /* 非递归的实现方式 */
  let res = [];
  if (root == null) return res;
  let queue = [root];
  // while 循环控制从上向下一层层遍历
  while (queue.length) {
    let size = queue.length;
    // 记录这一层的节点值
    let level = [];
    // for 循环控制每一层从左向右遍历
    for (let i = 0; i < size; i++) {
      let cur = queue.shift();
      level.push(cur.val);
      if (cur.left != null) queue.push(cur.left);
      if (cur.right != null) queue.push(cur.right);
    }
    res.push(level);
  }
  return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 二叉树的前序遍历【L144】

  1. 递归实现
var preorderTraversal = function(root, array = []) {
  if (root) {
    array.push(root.val);
    preorderTraversal(root.left, array);
    preorderTraversal(root.right, array);
  }
  return array;
};
1
2
3
4
5
6
7
8
  1. 迭代实现
var preorderTraversal = function(root) {
  const result = [];
  const stack = [];
  let current = root;
  while (current || stack.length > 0) {
    while (current) {
      result.push(current.val);
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    current = current.right;
  }
  return result;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 二叉树的中序遍历【L94】

  1. 递归实现
var inorderTraversal = function(root, array = []) {
  if (root) {
    inorderTraversal(root.left, array);
    array.push(root.val);
    inorderTraversal(root.right, array);
  }
  return array;
};
1
2
3
4
5
6
7
8
  1. 迭代实现
var inorderTraversal = function(root) {
  const result = [];
  const stack = [];
  let current = root;
  while (current || stack.length > 0) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    result.push(current.val);
    current = current.right;
  }
  return result;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 二叉树的后序遍历【L145】

  1. 递归实现
var postorderTraversal = function(root, array = []) {
  if (root) {
    postorderTraversal(root.left, array);
    postorderTraversal(root.right, array);
    array.push(root.val);
  }
  return array;
};
1
2
3
4
5
6
7
8
  1. 迭代实现
// 非递归实现:我们需要先遍历右子树,再遍历左子树
var postorderTraversal = function(root) {
  // 初始化数据
  const result = [];
  const stack = [];
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      result.unshift(root.val); // 添加到数组开头
      root = root.right;
    }
    root = stack.pop();
    root = root.left;
  }
  return result;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 二叉树的最大深度【L104】

  1. 递归实现

时间复杂度:O(n)

var maxDepth = function(root) {
  if (!root) {
    return 0;
  } else {
    const left = maxDepth(root.left);
    const right = maxDepth(root.right);
    return Math.max(left, right) + 1;
  }
};
1
2
3
4
5
6
7
8
9
  1. 迭代实现
var maxDepth = function(root) {
  if (root == null) return 0;
  let queue = [];
  queue.push(root);
  let ans = 0;
  while (queue.length) {
    let size = queue.length;
    for (let i = 0; i < size; i++) {
      // 队头出队列
      let node = queue.shift();
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    ans += 1;
  }
  return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 合并二叉树 【L617】

  1. 递归实现
var mergeTrees = function(root1, root2) {
  // 如果一棵树有,另一棵树没有,接上去
  if (root1 == null) return root2;
  if (root2 == null) return root1;
  // 两棵树都有的节点,叠加节点值
  root1.val += root2.val;
  // 递归合并左右子树
  root1.left = mergeTrees(root1.left, root2.left);
  root1.right = mergeTrees(root1.right, root2.right);
  return root1;
};
1
2
3
4
5
6
7
8
9
10
11
  1. 迭代实现
var mergeTrees = function(root1, root2) {
  // 确定终止条件,如果root1 为空,合并后就为root2
  if (!root1) return root2;
  // 确定终止条件,如果root2 为空,合并后就为root1
  if (!root2) return root1;
  const queue = [root1, root2];
  while (queue.length) {
    const node1 = queue.shift();
    const node2 = queue.shift();
    // 此时两个节点一定不为空,val相加
    node1.val += node2.val;
    // 如果两棵树左节点都不为空,加入队列
    if (node1.left !== null && node2.left !== null) {
      queue.push(node1.left);
      queue.push(node2.left);
    }
    // 如果两棵树右节点都不为空,加入队列
    if (node1.right !== null && node2.right !== null) {
      queue.push(node1.right);
      queue.push(node2.right);
    }
    // 当root1的左节点 为空 root2的左节点直接合并
    if (node1.left === null) {
      node1.left = node2.left;
    }
    // 当root1的右节点 为空 root2右节点直接合并
    if (node1.right === null) {
      node1.right = node2.right;
    }
  }
  return root1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 二叉搜索树的第 k 大节点【O54】

问题描述:给定一棵二叉搜索树,请找出其中第 k 大的节点的值。

解法基于此性质:二叉搜索树的中序遍历为 递增序列,二叉搜索树的中序遍历倒序为 递减序列,第 K 大也就是递减序列数组的 arr[k-1],

  1. 递归-逆中序遍历(右节点->根节点->左节点)
var kthLargest = function(root, k) {
  const arr = [];
  function dfs(node) {
    if (!node) return;
    dfs(node.right);
    arr.push(node.val);
    dfs(node.left);
  }
  dfs(root);

  return arr[k - 1];
};
1
2
3
4
5
6
7
8
9
10
11
12
  1. 迭代解法
var kthLargest = function(root, k) {
  // 反向中序遍历
  let stack = [],
    cur = root;
  while (stack.length > 0 || cur != null) {
    while (cur) {
      stack.push(cur);
      cur = cur.right;
    }
    cur = stack.pop();
    k--;
    if (k == 0) {
      return cur.val;
    }

    cur = cur.left;
  }
  return null;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 翻转二叉树 【L216】

  1. 递归

时间复杂度:O(N),其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点,对每个节点而言,我们在常数时间内交换其两棵子树。

空间复杂度:O(N)。使用的空间由递归栈的深度决定,它等于当前节点在二叉树中的高度。在平均情况下,二叉树的高度与节点个数为对数关系,即 O(logN)。而在最坏情况下,树形成链状,空间复杂度为 O(N)。

var invertTree = function(root) {
  if (root === null) {
    return null;
  }
  const left = invertTree(root.left);
  const right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
};
1
2
3
4
5
6
7
8
9
10
更新时间: 1/25/2022, 8:44:55 PM
树概览
链表概览

← 树概览 链表概览→

最近更新
01
前端权限管理
02-24
02
vue2指令
02-24
03
vue2 hook
02-24
更多文章>
Theme by Vdoing | Copyright © 2019-2022 放肆青春
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式