树

理解树结构

树的关键特性和重点概念

• 树的层次计算规则：根结点所在的那一层记为第一层，其子结点所在的就是第二层，以此类推。
• “度”的概念：一个结点开叉出去多少个子树，被记为结点的“度”。比如我们上图中，根结点的“度”就是 3。
• “叶子结点”：叶子结点就是度为 0 的结点。在上图中，最后一层的结点的度全部为 0，所以这一层的结点都是叶子结点。
• 结点和树的“高度”计算规则：叶子结点高度记为 1，每向上一层高度就加 1，逐层向上累加至目标结点时，所得到的的值就是目标结点的高度。树中结点的最大高度，称为“树的高度”。

理解二叉树结构

二叉树是指满足以下要求的树

• 它可以没有根结点，作为一棵空树存在
• 如果它不是空树，那么必须由根结点、左子树和右子树组成，且左右子树都是二叉树

二叉树的编码实现

function TreeNode(val) {
  this.val = val //数据域
  this.left = null //左树的引用
  this.right = null // 右树的引用
}

二叉树的遍历

以一定的顺序规则，逐个访问二叉树的所有结点，这个过程就是二叉树的遍历

• 递归遍历
  • 先序遍历
  • 中序遍历
  • 后序遍历
• 迭代遍历
  • 层次遍历

递归遍历

编程语言中，函数 Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。

• 根结点 -> 左子树 -> 右子树
• 左子树 -> 根结点 -> 右子树
• 左子树 -> 右子树 -> 根结点

所谓的“先序”、“中序”和“后序”，“先”、“中”、“后”其实就是指根结点的遍历时机

const root = {
  val: 'A',
  left: {
    val: 'B',
    left: {
      val: 'D'
    },
    right: {
      val: 'E'
    }
  },
  right: {
    val: 'C',
    right: {
      val: 'F'
    }
  }
}
// 所有遍历函数的入参都是树的根结点对象
function preorder(root) {
  // 递归边界，root 为空
  if (!root) {
    return
  }

  // 输出当前遍历的结点值
  //console.log('当前遍历的结点值是：', root.val) 先续
  // 递归遍历左子树
  preorder(root.left)
  // 输出当前遍历的结点值
  //console.log('当前遍历的结点值是：', root.val) 中序
  // 递归遍历右子树
  preorder(root.right)
  // 输出当前遍历的结点值
  //console.log('当前遍历的结点值是：', root.val)  后序
}

每个节点过了 2 次 等到没有左右子节点才根据先中后在第二次打印对应当前节点

编写一个递归函数之前，大家首先要明确两样东西

• 递归式
• 递归边界

TIP

前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点

TIP

二叉树的所有问题，就是让你在前中后序位置注入巧妙的代码逻辑，去达到自己的目的

TIP

二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。

TIP

但这里面大有玄妙，意味着前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。