📚 树

为什么有树这个数据结构？假设递归求斐波那契数列f(n) = f(n-1) + f(n-2)，如果把整个计算过程展开，你会发现这是一棵树。像 html，dom 节点展开后是一棵树。
如果树是无序的，查找元素是O(n)
如果树是有序的（二叉搜索树），查找元素是O(logn)，类似于二分查找。假设一棵树所有结点都只有右节点，它就退化成链表，查询时间复杂度退化为O(n)

  • 二叉搜索树

    • 左子树的所有节点小于根节点
    • 右子树的所有节点大于根节点
    • 左右子树也是二叉搜索树

  • 二叉树的遍历方式

    • 前序遍历：根节点 -> 左子树 -> 右子树
    • 中序遍历：左子树 -> 根节点 -> 右子树
    • 后序遍历：左子树 -> 右子树 -> 根节点

  • 节点定义

1
2
3
4
5
function TreeNode(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}


🏫 二叉树的遍历 - 代码模板

树的解题方法一般都是递归，因为每个节点的结构相同，当你想访问左节点时，最好的方式是对左节点再调用一遍函数。

  • 前序遍历
1
2
3
4
5
6
const preorder = (node) => {
  if (!node) return;
  path.push(node.val);
  preorder(node.left);
  preorder(node.right);
};
  • 中序遍历
1
2
3
4
5
6
const inorder = (node) => {
  if (!node) return;
  inorder(node.left);
  path.push(node.val);
  inorder(node.right);
};
  • 后序遍历
1
2
3
4
5
6
const backorder = (node) => {
  if (!node) return;
  backorder(node.left);
  backorder(node.right);
  path.push(node.val);
};


🌲 递归与树

在函数体里调用函数本身，称为递归。把递归的全过程剥开，你会发现它是一个树结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 斐波那契
function f(n) {
  if (n === 0 || n === 1) return n;
  return f(n - 1) + f(n - 2);
}

// 把它剥开，发现是一个树结构
f(6);
6 * f(5);
6 * 5 * f(4);
6 * 5 * 4 * f(3);
6 * 5 * 4 * 3 * f(2);
6 * 5 * 4 * 3 * 2 * f(1);
6 * 5 * 4 * 3 * 2 * 1;


🏫 经典题目

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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
preorder = [3,9,2,1,7]
inorder = [9,3,1,2,7]
输出：[3,9,2,null,null,1,7]

1
2
3
4
5
  3
 / \
9  2
  /  \
 1   7

preorder [3,9,2,1,7] 根节点，左子树，右子树
[3 - 根节点， 9 - 左子树的preorder， 2,1,7 - 右子树的preorder]
inorder [9,3,1,2,7] 左子树，根节点，右子树
[9 - 左子树的inorder， 3 - 根节点， 1,2,7 - 右子树的inorder]

1
2
3
4
5
6
7
8
9
10
11
12
var buildTree = function (preorder, inorder) {
  if (inorder.length === 0) return null;

  const root = new TreeNode(preorder[0]);
  const mid = inorder.indexOf(preorder[0]);
  // 分治
  // node.left 传入左子树的 preorder, inorder
  root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
  // node.right 传入右子树的 preorder, inorder
  root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));
  return root;
};