手把手带你刷二叉树（一期）

我们之前强调过，先刷二叉树的题目，因为很多经典算法以及我们之前讲过的回溯、动态规划、分治都是树的问题，而树的问题永远逃不开树的递归遍历框架：

// 二叉树遍历框架
function traverse(root: TreeNode): void {
  // 前序遍历
  traverse(root.left)
  // 中序遍历
  traverse(root.right)
  // 后序遍历
}

行云流水地写递归代码是学好算法的基本功，而二叉树相关的题目就是最练习递归基本功的，最练习框架思维的。

二叉树的重要性

举个例子，比如我们的经典算法「快速排序」和「归并排序」，对于这两个算法，你有什么理解？ 如果你告诉我，快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历，那么我就知道你是个算法高手了。

很多算法都是由简单的底层慢慢堆砌而成，如果你能一眼识破这些算法的底细，解决算法问题自然就迎刃而解。

写递归算法的秘诀

我们曾经说过， 写递归算法的关键是要明确函数的「定义」是什么，然后相信这个定义，利用这个定义推导最后结果，绝不要跳入递归的细节。

怎么理解，我们用一个具体的例子来说，比如让你计算一棵二叉树的节点数：

function count(root: TreeNode): number {
  // base case
  if(!root) return 0
  // 自己加上子树的节点数就是整棵树的节点数
  return 1 + count(root.left) + count(root.right)
}

问题非常简单，就是当前节点数加上他的左子树上的节点数和右子树节点数的和，而左右子树的节点数则可以通过递归调用函数来解决。

写树相关算法，简单来说就是先搞清楚 root 节点该做什么，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情。