二叉树

数据结构与算法 评论
  • 一种分层数据的抽象模型，例如dom，菜单，树形控件，多层联动选择器
  • JavaScript中没有树，但是可以用Object和Array构建树
  • 常见操作 深度/广度有限遍历，先中后序遍历
  • 二叉树: 树中的每个节点最多只能两个子节点，在JavaScript 中使用Object进行模拟

深度优先遍历

含义： 尽可能深的搜索树的分支

1
2
3
4
5
// 深度优先遍历
function inter1(tree) {
  console.log(tree.value);
  tree.child.map(e => inter(e)) // 递归调用
}

广度优先遍历

含义： 先访问离根节点最近的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
// 广度优先遍历
function inter2(tree) {
  const q = [tree] // 使用队列存储广度数据
  while (q.length > 0) {
    let c = q.shift() // 每次取队列最后一个
    console.log(c.value);
    c.child.forEach(e => {
      q.push(e) // 再次将下一层数据加入队列
    })
  }
}

inter2(tree)

先序遍历二叉树

定义：先根节点，后左子树，再右子树

1
2
3
4
5
6
7
8
9
// 先序遍历
function preorder(root) {
  if (!root) {
    return
  }
  console.log(root.key); // 首先访问
  preorder(root.left)
  preorder(root.right)
}

中序遍历二叉树

定义：先左子树，后根节点，再右子树

1
2
3
4
5
6
7
8
9
// 中序遍历
function inorder(root) {
  if (!root) {
    return
  }
  inorder(root.left)
  console.log(root.key);
  inorder(root.right)
}

后序遍历二叉树

定义：先左子树，后右子树，再根节点

1
2
3
4
5
6
7
8
9
// 后序遍历
function postorder(root) {
  if (!root) {
    return
  }
  postorder(root.left)
  postorder(root.right)
  console.log(root.key);
}

先序遍历二叉树（非递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 先序遍历
function preorder(root) {
  if (!root) return
  const task = [root]
  while (task.length) {
    const n = task.pop()
    console.log(n.key);
    if (n.right) task.push(n.right)
    if (n.left) task.push(n.left)
    // pop拿最后面的,数组需要保证后进先出,所以left放后面,这样每次循环都会优先使用left,直到left用完,就会用right,当前层级全部用完就会到更加深处或者右边的二叉树
  }
}

preorder(bt)

中序遍历二叉树（非递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function inorder(root) {
  if (!root) return
  const task = []
  let p = root
  while (task.length || p) {
    while (p) {
      task.push(p)
      p = p.left
    }
    const n = task.pop()
    console.log(n.key);
    p = n.right
  }
}

inorder(bt)
// 首先找到最右边的全部节点,在从最左边开始递归
// 在每次将右节点放入下一次循环,因为当前一定是中节点
// 右节点完成后找上的中节点,中节点完成后找下右节点,完成二叉树的从左到右的覆盖
// task存储所有左节点,当前阶段存在右节点的情况下,数组最后一位是右节点,下次一定会被抛出
// p存储下一个右节点,开始下级树的查询

后序遍历二叉树（非递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 后序遍历(非递归)
function postorder(root) {
  if (!root) return
  const task = [root]
  const outputTask = []
  while (task.length) {
    const n = task.pop()
    outputTask.push(n.key)
    if (n.left) task.push(n.left)
    if (n.right) task.push(n.right)
  }
  while (outputTask.length) {
    let n = outputTask.pop()
    console.log(n);
  }
}
// 后序的顺序是 先右 再左 再中 首先倒叙先序遍历,获取先中 再左 再右
// 最后倒序输出
postorder(bt)

题目 二叉树的最大深度

https://www.youtube.com/watch?v=H8SjbVxGB1c&list=PLwIrqQCQ5pQmjH6YyFvH2A9FYL6bBB4Ra

时间复杂度：O(n)

空间复杂度：O(n)

思路：使用深度优先遍历（先序）,记录最大递归数量，最后返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
  let res = 0
  /**
   * 
   * @param {*} n 树
   * @param {*} l 层级
   */
  const dfs = (n, l) => {
    if (!n) return
    if (!n.left && !n.right) {
      res = Math.max(res, l)
    }
    dfs(n.left, l + 1)
    dfs(n.right, l + 1)
  }
  dfs(root, 1)
  return res
};

题目 二叉树的最小深度

时间复杂度：O(n)

空间复杂度：O(n)

思路：广度遍历，同时记录当前层级，当遇到没有叶子节点，则说明找到最小深度，最后返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function (root) {
  if (!root) return 0;
  let task = [
    [root, 1]
  ]
  while (task.length) {
    let [n, l] = task.shift()
    if (!n.left && !n.right) {
      return l
    }
    if (n.right) task.push([n.right, l + 1])
    if (n.left) task.push([n.left, l + 1])

  }
};

题目 二叉树的层序遍历（广度遍历解法）

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

时间复杂度：O(n)

空间复杂度：O(n)

思路：广度遍历二叉树，同时记录当前层级，以层级为数组下标，完成层序遍历结果记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  if (!root) return []
  let task = [
    [root, 0]
  ]
  let res = []
  while (task.length) {
    let [n, level] = task.shift()
    if (!res[level]) {
      res.push([n.val])
    } else {
      res[level].push(n.val)
    }
    if (n.left) task.push([n.left, level + 1])
    if (n.right) task.push([n.right, level + 1])
  }
  return res
};

题目 二叉树的层序遍历（新陈代谢+广度遍历解法）

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

时间复杂度：O(n)

空间复杂度：O(n)

思路：广度遍历二叉树，在遍历中，每次都将本层级全部遍历完成，再进行下一个层级的遍历，这样在同一个循环里面把当前数据都放入遍历结果的最后，循环累加完成结果记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  if (!root) return []
  const q = [root]
  const res = []
  while (q.length) {
    let len = q.length
    res.push([])
    // 每次while之前都把上一层的全部提出,下一层的全部记录下来
    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
};

题目 二叉树的中序遍历(递归)

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

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
  const res = []
  const rec = (n) => {
    if (!n) return;
    rec(n.left)
    res.push(n.val)
    rec(n.right)
  }
  rec(root)
  return res
};

题目 二叉树的中序遍历(非递归)

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

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
  const res = []
  const task = [] // 遍历数据
  let p = root // 指针
  while (task.length || p) {
    // 找到所有左子树
    while (p) {
      task.push(p)
      p = p.left
    }
    // 获取最后一个节点 初始化的时候都是左子树 后面可能为右子树
    const n = task.pop()
    res.push(n.val)
    p = n.right
  }
  return res
};

题目 路径总和

https://leetcode-cn.com/problems/path-sum/

时间复杂度：O(n)

空间复杂度：O(n)

思路：使用深度遍历所有节点的值，在这个过程中不断累加，直到遇到最底部节点，对比与目标是否一致，如果一致则说明有，没有则继续找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {
  if (!root) return false;
  let res = false
  const dfs = (n, s) => {
    // console.log(n.val);
    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 false
};

深度优先遍历json的全部节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const json = {
  a: {
    b: {
      c: 1
    }
  },
  d: [1, 2]
}

function dfs(json, path) {
  console.log(json, path);
  Object.keys(json).map(e => {
    dfs(json[e], path.concat(e))
  })
}

dfs(json, [])

bluedancersWeb Developer & Product Manager

一切都是为了实现技术的价值