跳至主要內容

树

Mr.Chen数据结构与算法树大约 8 分钟约 2499 字

简介

一种分层数据的抽象模型

js 中没有树，但是可以用Object和Array构建树

树的常用操作：深度/广度优先遍历,先中后序遍历

深度与广度优先遍历

深度优先遍历

尽可能深的搜索树的分支

深度优先遍历
深度优先遍历

深度优先遍历算法口诀：

访问根节点

对根节点的children挨个进行深度优先遍历。

::: details 深度优先遍历 dfs

/**
 * 深度优先遍历 dfs
 */
const tree = {
  val: 'a',
  children: [
    {
      val: 'b',
      children: [
        {
          val: 'd',
          children: [],
        },
        {
          val: 'e',
          children: [],
        },
      ],
    },
    {
      val: 'c',
      children: [
        {
          val: 'f',
          children: [],
        },
        {
          val: 'g',
          children: [],
        },
      ],
    },
  ],
}

const dfs = (root) => {
  if (!root) return
  console.log(root.val)
  root.children.forEach(dfs)
}
dfs(tree)
// a
// b
// d
// e
// c
// f
// g

:::

广度优先遍历

先访问离根节点最近的节点

广度优先遍历
广度优先遍历

广度优先遍历算法口诀：

  1. 新建一个队列，把根节点入队。
  2. 把队头出队并访问。
  3. 把队头的children挨个入队。
  4. 重复第二、三步，直到队列为空。

::: details 广度优先遍历 bfs

/**
 * 广度优先遍历 bfs
 */
const tree = {
  val: 'a',
  children: [
    {
      val: 'b',
      children: [
        {
          val: 'd',
          children: [],
        },
        {
          val: 'e',
          children: [],
        },
      ],
    },
    {
      val: 'c',
      children: [
        {
          val: 'f',
          children: [],
        },
        {
          val: 'g',
          children: [],
        },
      ],
    },
  ],
}
const bfs = (root) => {
  if (!root) return
  const q = [root]
  while (q.length > 0) {
    const n = q.shift()
    console.log(n.val)
    n.children.forEach((child) => q.push(child))
  }
}
bfs(tree)
// a
// b
// c
// d
// e
// f
// g

:::

二叉树的先中后序遍历

二叉树:树中每个节点最多只能有两个子节点

二叉树
二叉树

一个普普通通的二叉树

const bt = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 3,
      left: null,
      right: null,
    },
    right: {
      val: 4,
      left: {
        val: 5,
        left: 5,
      },
      right: null,
    },
  },
  right: {
    val: 6,
    left: null,
    right: {
      val: 7,
      left: null,
      right: null,
    },
  },
}
module.exports = bt

先序遍历算法口诀

  1. 访问根节点
  2. 对根节点的左子树进行先序遍历
  3. 对根节点的右子树进行先序遍历

::: details preorder

/**
 * preorder 先序遍历
 */
const bt = require('./bt')

const preorder = (root) => {
  if (!root) return
  console.log(root.val)
  preorder(root.left)
  preorder(root.right)
}

preorder(bt)

// 1
// 2
// 3
// 4
// 5
// 6
// 7

:::

中序遍历算法口诀

对根节点的左子树进行中序遍历

访问根节点

对根节点的右子树进行中序遍历

::: details inorder

/**
 * inorder 中序遍历
 */

const bt = require('./bt')

const inorder = (root) => {
  if (!root) return
  inorder(root.left)
  console.log(root.val)
  inorder(root.right)
}
inorder(bt)
// 3
// 2
// 5
// 4
// 1
// 6
// 7

:::

后序遍历算法口诀

对根节点的左子树进行后序遍历

对根节点的右子树进行后序遍历

访问根节点

::: details postorder

/**
 * postorder 后序遍历
 */
const bt = require('./bt')

const postorder = (root) => {
  if (!root) return
  postorder(root.left)
  postorder(root.right)
  console.log(root.val)
}
postorder(bt)
// 3
// 5
// 4
// 2
// 7
// 6
// 1

:::

先中后序遍历非递归版

::: tip 提示 画个栈理解 :::

::: details 先序遍历

const preorder = (root) => {
  const stack = [root]
  while (stack.length) {
    const n = stack.pop()
    console.log(n.val)
    // 栈：先进后出,所以应该先把右子树入栈。
    if (n.right) stack.push(n.right)
    if (n.left) stack.push(n.left)
  }
}
preorder(bt)

:::

::: details 中序遍历

const inorder = (root) => {
  if (!root) return
  const stack = []
  let p = root
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    console.log(n.val)
    p = n.right
  }
}
inorder(bt)

:::

::: tip 提示 先序遍历：根—>左—>右,后序倒过来：左—>右—>根

先先序遍历，然后利用另外一个栈，倒序输出 :::

::: details 后序遍历

const postorder = (root) => {
  if (!root) return
  const outputStack = []
  const stack = [root]
  while (stack.length) {
    const n = stack.pop()
    // 压入输出栈
    outputStack.push(n)
    if (n.left) stack.push(n.left)
    if (n.right) stack.push(n.right)
  }
  while (outputStack.length) {
    const n = outputStack.pop()
    console.log(n.val)
  }
}
postorder(bt)

:::

LeetCode：144. 二叉树的前序遍历

LeetCode：144. 二叉树的前序遍历open in new window

::: details code

/*
 * @lc app=leetcode.cn id=144 lang=javascript
 *
 * [144] 二叉树的前序遍历
 */

// @lc code=start
/**
 * 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) {
  if (!root) return []
  let stack = [root]
  let res = []
  while (stack.length) {
    const n = stack.pop()
    res.push(n.val)
    if (n.right) stack.push(n.right)
    if (n.left) stack.push(n.left)
  }
  return res
}
// @lc code=end

:::

LeetCode：145. 二叉树的后序遍历

LeetCode：145. 二叉树的后序遍历open in new window ::: details code

/*
 * @lc app=leetcode.cn id=145 lang=javascript
 *
 * [145] 二叉树的后序遍历
 */

// @lc code=start
/**
 * 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 postorderTraversal = function (root) {
  if (!root) return []
  let stack = [root]
  let outputStack = []
  while (stack.length) {
    const n = stack.pop()
    outputStack.push(n.val)
    if (n.left) stack.push(n.left)
    if (n.right) stack.push(n.right)
  }
  let res = []
  while (outputStack.length) {
    const n = outputStack.pop()
    res.push(n)
  }
  return res
}
// @lc code=end

:::

LeetCode：104. 二叉树的最大深度

LeetCode：104. 二叉树的最大深度open in new window

  • 解题思路

求最大深度，考虑使用深度优先遍历。

在深度优先遍历过程中，记录每个节点所在的层级，找出最大的层级即可。

  • 解题步骤

新建一个变量，记录最大深度。

深度优先遍历整棵树，并记录每个节点的层级，同时不断刷新最大深度这个变量。

遍历结束返回最大深度这个变量

::: details code

/*
 * @lc app=leetcode.cn id=104 lang=javascript
 *
 * [104] 二叉树的最大深度
 */

// @lc code=start
/**
 * 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 maxDepth = function (root) {
  if (!root) return 0
  let dep = 0
  const dfs = (n, d) => {
    if (!n) return
    // 只有节点是叶子节点才会刷新dep
    if (!n.left || !n.right) dep = Math.max(dep, d)
    if (n.left) dfs(n.left, d + 1)
    if (n.right) dfs(n.right, d + 1)
  }
  dfs(root, 1)
  return dep
}
// @lc code=end

:::

LeetCode：111. 二叉树的最小深度

LeetCode：111. 二叉树的最小深度open in new window

  • 解题思路

求最小深度，考虑使用广度优先遍历。

在广度优先遍历过程中，遇到叶子节点，停止遍历，返回节点层级。

  • 解题步骤

广度优先遍历整棵树，并记录每个节点的层级

遇到叶子节点，返回节点层级，停止遍历

::: details code

/*
 * @lc app=leetcode.cn id=111 lang=javascript
 *
 * [111] 二叉树的最小深度
 */

// @lc code=start
/**
 * 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 minDepth = function (root) {
  if (!root) return 0
  const q = [[root, 1]]
  while (q.length) {
    const [n, d] = q.shift()
    if (!n.left && !n.right) return d //
    if (n.left) q.push([n.left, d + 1])
    if (n.right) q.push([n.right, d + 1])
  }
}
// @lc code=end

:::

LeetCode：102. 二叉树的层序遍历

LeetCode：102. 二叉树的层序遍历open in new window

  • 解题思路

层序遍历顺序就是广度优先遍历。

不过在遍历时候需要记录当前节点所处的层级，方便将其添加到不同的数组中

  • 解题步骤

广度优先遍历二叉树。

遍历过程中，记录每个节点的层级，并将其添加到不同的数组中。

::: details 解法 1

/*
 * @lc app=leetcode.cn id=102 lang=javascript
 *
 * [102] 二叉树的层序遍历
 */

// @lc code=start
/**
 * 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 levelOrder = function (root) {
  if (!root) return []
  const q = [[root, 0]]
  let res = []
  while (q.length) {
    const [n, d] = q.shift()
    if (!res[d]) {
      res.push([n.val])
    } else {
      res[d].push(n.val)
    }
    if (n.left) q.push([n.left, d + 1])
    if (n.right) q.push([n.right, d + 1])
  }
  return res
}
// @lc code=end

:::

::: details 解法 2

/*
 * @lc app=leetcode.cn id=102 lang=javascript
 *
 * [102] 二叉树的层序遍历
 */

// @lc code=start
/**
 * 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 levelOrder = function (root) {
  if (!root) return []
  const q = [root]
  let res = []
  while (q.length) {
    let len = q.length
    res.push([])
    while (len--) {
      const n = q.shift()
      res[res.length - 1].push(n.val)
      if (n.left) q.push(n.left)
      if (n.right) q.push(n.right)
    }
  }
  return res
}
// @lc code=end

:::

LeetCode：94. 二叉树的中序遍历

LeetCode：94. 二叉树的中序遍历open in new window

::: details 递归

/*
 * @lc app=leetcode.cn id=94 lang=javascript
 *
 * [94] 二叉树的中序遍历
 */

// @lc code=start
/**
 * 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 inorderTraversal = function (root) {
  if (!root) return []
  const res = []
  const rec = (n) => {
    if (!n) return
    rec(n.left)
    res.push(n.val)
    rec(n.right)
  }
  rec(root)
  return res
}
// @lc code=end

:::

::: details 迭代

/*
 * @lc app=leetcode.cn id=94 lang=javascript
 *
 * [94] 二叉树的中序遍历
 */

// @lc code=start
/**
 * 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 inorderTraversal = function (root) {
  if (!root) return []
  let stack = []
  let res = []
  let p = root
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    res.push(n.val)
    p = n.right
  }
  return res
}
// @lc code=end

:::

LeetCode：112. 路径总和

LeetCode：112. 路径总和open in new window

  • 解题思路

    在深度优先遍历的过程中，记录当前路径的节点值的和。

    在叶子节点处，判断当前路径的节点值的和是否等于目标值。

  • 解题步骤

    深度优先遍历二叉树，在叶子节点处，判断当前路径的节点值的和是否等于目标值是就返回 true

    遍历结束，如果没有匹配，就返回 false

::: details code

/*
 * @lc app=leetcode.cn id=112 lang=javascript
 *
 * [112] 路径总和
 */

// @lc code=start
/**
 * 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
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {
  if (!root) return false
  let res = false
  const dfs = (n, s) => {
    if (!n) return
    if (!n.left && !n.right && targetSum === s) {
      res = true
    }
    if (n.left) dfs(n.left, s + n.left.val)
    if (n.right) dfs(n.right, s + n.right.val)
  }
  dfs(root, root.val)
  return res
}
// @lc code=end

:::

前端与树：遍历 JSON 的所有节点值

const json = {
  a: { b: { c: 1 } },
  d: [1, 2],
}
const dfs = (n, path) => {
  console.log(n, path)
  Object.keys(n).forEach((k) => {
    dfs(n[k], path.concat(k))
  })
}
dfs(json, [])
// { a: { b: { c: 1 } }, d: [ 1, 2 ] } []
// { b: { c: 1 } } [ 'a' ]
// { c: 1 } [ 'a', 'b' ]
// 1 [ 'a', 'b', 'c' ]
// [ 1, 2 ] [ 'd' ]
// 1 [ 'd', '0' ]
// 2 [ 'd', '1' ]
上次编辑于:
Copyright © 2018-present Mr.Chen