我们之前已经学习了线性表基础部分（链表、栈、队列），接下来我们来学习二叉树基础。

概念

一、结构定义

在现实生活中，树都是树根在下，树苗在上，像这样——🌲。但是在数据结构中，你应该将其想象成一颗树根在顶端的树，它就像下面这张图一样。

我们本次学习的二叉树是在其结点（node）上会存在着左结点和右结点而形成了一颗树的结构。
我们来看这样的一个二叉树的结构表示图 👇

其中结点1（结点值为1的那个结点）为树的根结点，其左孩子（左子树）为结点2，右孩子（右子树）为结点3，其他结点以此类推……
我们用代码的形式来表示一下

// 先封装
class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val || 0
    this.left = left || null
    this.right = right | null
  }
}
// 为了方便观看，我这里值与变量 node* 一致
const node1 = new TreeNode(1)
const node2 = new TreeNode(2)
const node3 = new TreeNode(3)
const node4 = new TreeNode(4)
const node5 = new TreeNode(5)
const node6 = new TreeNode(6)
node1.left = node2, node1.right = node3
node2.left = node4, node2.right = node5
node3.right = node6

你会发现，这跟我们之前学的链表非常相似，唯一不同的就是链表只有一个指针，而二叉树会存在两个指针

二、遍历概念

在二叉树中最重要的操作就是遍历了，最基本的就是前序遍历，中序遍历，后序遍历，这三种遍历方式的规则如下

解释一下就是，前序遍历就是先访问到根结点的值，再去访问左子树，最后访问右子树，中序遍历与后序遍历就是换一下位置，也许你还没明白，那我们就拿上面那个二叉树的结构来画图说明一下。

三、还原二叉树

我们看上面的这个图，在前序遍历时，根结点在第一个位置，左子树次之，右子树再次之。
而在中序遍历时，根结点在中间，左右子树分别在两边。
这样当我们将这两种遍历结合起来看

可以发现，我们能确定前序遍历中第一个结点值 1 就是根结点，那么就能在中序遍历中确定 1 的左右两边的值分别是左右子树的值。即根结点为 1，左子树的结点们就是 4 2 5，右子树的结点们就是 3 6。

同样对于 4 2 5 这三个结点，根据这个规律就能找到左子树的根结点为 2 ，左子树的左结点为 4，左子树的右结点为 5 ，如下👇

那么自然而然的我们就能将右子树的结构还原出来，右子树的根结点为 3 ，没有左结点，右子树的右结点为6 👇

总结一下根据前序 + 中序还原一颗二叉树的技巧（后序类似的，找最后一位就是根结点）：

1. 先找前序的第一位root
2. 在中序中找到root，其左右两边即左右子树的结点
3. 根据上面两点继续找子树的根结点和子树的左右结点

   实践

   重新认识递归

   在我们开始写代码之前，我想带着你重新学习一下递归算法。
   如果你以前写递归是把递归程序展开来看的话，希望你从今天起忘掉这种方式。请你记住下面👇这句话：

   在做递归时，如果 是正确的，那么就假设是正确的，接着就可以推导出也是正确的。由此推导出这个递归它的结果就是正确的，至于它到底是怎么展开执行的，不要去关注它！

我们来看一个以递归实现的 fibonacci 算法👇

function fibonacci(n: number) {
  if (n <= 2) return n
  return fibonacci(n - 1) + fibonacci(n - 2)
}

我们分析一下，当 n = 1 和 n = 2 的时候，是正确的返回，也就是我们的正确，就代表着边界条件。
接着我们假设fibonacci(n - 1) 能正确的算出 n - 1 的值，fibonacci(n - 2)能正确的算出 n - 2 的值，那么当这两个假设都成立时，fibonacci(n)也是成立的，这也就是我们假设的正确，那么我们就能推导出也是正确的。
由此，我们的整个递归就是正确的。你只需要把它当成另外一个函数来执行即可。

前序遍历

二叉树的前序遍历：

1. 函数意义：前序遍历以 root 为根节点的二叉树
2. 边界条件：root 为空时不需要遍历
3. 递归过程：前序遍历左子树，前序遍历右子树

那么我们根据这个条件来实现代码如下👇

// 前序遍历以 root 为根节点的二叉树
function preorder(root: TreeNode | null) {
  // 边界条件：root 为空不需要遍历
  if (!root) return
  console.log(root.val)
  // 前序遍历左子树
  preorder(root.left)
  // 前序遍历右子树
  preorder(root.right)
};

前序遍历作为 leetcode 题目 👉 144. 二叉树的前序遍历。要求前序遍历出二叉树的节点中的 val ，最后返回一个数组，去试试看吧～

中序遍历

其实这三种遍历的实现代码思想是一样的，我这里就再写一下中序遍历，后序遍历就不写了。

// 中序遍历以 root 为根节点的二叉树
function preorder(root: TreeNode | null) {
  // 边界条件：root 为空不需要遍历
  if (!root) return
  // 中序遍历左子树
  preorder(root.left)
  console.log(root.val)
  // 中序遍历右子树
  preorder(root.right)
};

同样也是leetcode题目 👉 94. 二叉树的中序遍历。另外后序遍历 题目为 145. 二叉树多后序遍历
这三种遍历方式非常简单，如果你仍不太明白，希望你能把上面的资料多看及多练几遍，另外隔一段时间就将leetcode 上的题目多练习几遍。

翻转二叉树

这是一道多年前 Max Howell 面试谷歌没有解出来的题，哈哈哈哈哈哈。leetcode 题目 👉 226. 翻转二叉树

function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return root; // 当二叉树为空时直接返回它（边界条件）
  // const temp = root.left
  // root.left = root.right
  // root.right = temp
  // 与下等同，下面这种写法记得在上面那句加上分号
  [root.left, root.right] = [root.right, root.left] // 将root的左右节点进行交换
  invertTree(root.left) // 翻转左子树（记住不要展开看，它就是能保证能将左子树翻转）
  invertTree(root.right) // 翻转右子树
  return root // 返回翻转后的结果
};

根据前（后）中序遍历结果还原二叉树

这题也就是 leetcode 题目 👉 105. 从前序与中序遍历序列构造二叉树

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  if (!preorder.length) return null // 边界条件
  // 根据前序遍历的第一位(root)找到它在中序遍历中的位置，那么在中序遍历中的该位置的左右两边就分别是左子树和右子树的节点了
  const rootIndex = inorder.indexOf(preorder[0])

  // 构建左子树的前序遍历和左子树的中序遍历
  const leftPreorder = [], leftInorder = []
  for (let i = 0; i < rootIndex; i++) {
    // 左子树的前序遍历（前序遍历的第一个是根结点，后面才是左子树）
    leftPreorder.push(preorder[i + 1])
    // 左子树的中序遍历
    leftInorder.push(inorder[i])
  }

  // 构建右子树的前序遍历和右子树的中序遍历
  const rightPreorder = [], rightInorder = []
  for (let i = rootIndex + 1; i < preorder.length; i++) {
    rightPreorder.push(preorder[i])
    rightInorder.push(inorder[i])
  }

  // 构建树同时递归的构建左子树和右子树
  return new TreeNode(preorder[0], buildTree(leftPreorder, leftInorder), buildTree(rightPreorder, rightInorder))
};

这个题会稍微复杂一点，但如果你将上面的概念搞清楚了，仔细推敲一番，其实这题也不难做。

OK，二叉树其实远远不止文中这么轻描淡写这几下子就能写得完的，也是因为我个人水平有限以及时间原因，这一篇就到这儿了，后续还是会更二叉树相关的知识，这节就到这儿了