Siykt的博客TS 实现 BinaryTree（二叉树）与其经典算法
Contents
TS 实现 BinaryTree（二叉树）与其经典算法
最近金三银四的面试潮，想必大家都想在面试中拿到一个好的 offer，但是面试的时候，面试官问到树的遍历或者与之相关一些经典算法，你会怎么回答呢？如果你不会，那么这篇文章就是为你准备的，本文将会带你了解树的基本概念、树的遍历以及树的一些经典算法，希望能帮助到你。
Tree 的基本概念
先和大家聊一些基本的概念：
树是数据结构中比较重要也是比较难理解的一类存储结构，它的结构是一种非线性存储结构，存储的是具有一对多关系的数据元素的集合。
示例 1
1
/ \
2 3
/ \ / \
4 5 6 7
将具有一对多关系的集合中的数据元素按照示例的形式进行存储，整个存储形状在逻辑结构上看，类似于实际生活中倒着的树，所以称这种存储结构为"树型"存储结构。
节点
使用树结构存储的每一个数据元素都被称为节点，树节点同 链表节点 类似 (链式存储结构)，也是由两大部分组成：一个是用于存储数据的元素域，一个是用于存储指针信息的链接域。
每一个非空树都有且只有一个被称为根的节点，只要一个节点不存在父节点，那么它就是该树的根节点，而任何没有子节点的节点称为叶节点。
用 TS 实现：
/**
* 树节点(二叉树)
*
* 树节点同链表节点类似, 也是由两大部分组成
* 一个是用于存储数据的 <元素域>
* 一个是用于存储指针信息的 <链接域>
*/
export interface TreeNode<Data = number> {
// -- 元素域 --
/** 保存的数据 */
val: Data;
// -- 链接域 --
/** 指向左边的子元素 */
left: TreeNode<Data> | null;
/** 指向右边的子元素 */
right: TreeNode<Data> | null;
}
export class TreeNode<Data = number> {
constructor(public val: Data, public left: TreeNode<Data> | null = null, public right: TreeNode<Data> | null = null) {}
}
节点的度和层次
对于一个节点，拥有的子树数量 (节点有多少分支) 称为节点的度 (Degree)。如示例 1 中，每个节点的子节点都是 2 个即为 2 度。二叉树就是一颗只包含的 0、1、2 度节点组成的树。
而一棵树的深度是树中节点所在的最大的层次，也就是最深处的叶节点所处的位置。如示例中，最深处的叶节点的深度为 3，次树的深度亦为 3。
有序和无序
如果树中节点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树，反之称为无序树。在有序树中，一个节点最左边的子树称为"第一个孩子"，最右边的称为"最后一个孩子"。
二叉树
简单地理解，满足以下两个条件的树就是二叉树:
- 有序树。
- 只包含的 0、1、2 度节点。
二叉树 示例
1
/ \
2 3
/ \ /
4 5 6
二叉树的性质
从其特殊的结构我们可以总结出以下几个性质：
- 二叉树中，第 i 层最多有 $2^{(i - 1)}$ 个结点, 比如第 5 层最多能有
2 ** (5 - 1) = 16个结点。 - 如果二叉树的深度为 K，那么此二叉树最多有 $2^K-1$ 个结点，比如深度为 4 的二叉树最多有
2 ** 4 - 1 = 15个结点。 - 二叉树中，叶结点数（即度为 0 的节点）为 n0，度为 2 的结点数为 n2，则
n0 = n2 + 1。
满二叉树
当二叉树中除了终端结点，每个结点的度都为 2，则此二叉树称为满二叉树。
示例 1 即为满二叉树
作为特殊的二叉树，满二叉树还具有以下性质：
- 满二叉树中第 i 层的节点数为 $2^{(i - 1)}$ 个。
- 深度为 K 的满二叉树必有 $2^K-1$ 个节点。叶节点数为 $2^{(K - 1)}$。
- 满二叉树中不存在度为 1 的节点，每一个分支点中都是两棵深度相同的子树，且叶子节点都在最底层。
- 具有 n 个节点的满二叉树的深度为 $\log_2{(n+1)}$。
二叉树的遍历
说了这么多还没给 xdm 看多少代码，不多废话了，直接上代码：
再废话一句 😁，二叉树的遍历是有技巧的，只要我们掌握一些递归的思想，就能很快的写各种姿势的遍历啦。
- 前序遍历，对应的 LeetCode 地址：144. 二叉树的前序遍历 - 力扣（LeetCode）Ï
/**
* 二叉树的前序遍历
* @param root 根节点
*/
export function preorderTraversal(root: TreeNode | null) {
let res: number[] = [];
if (root) {
// 在遍历完所有节点之前 提交 val 就是后序遍历
res.push(root.val);
if (root.left) {
res = res.concat(preorderTraversal(root.left));
}
if (root.right) {
res = res.concat(preorderTraversal(root.right));
}
}
return res;
}
/**
* 二叉树的中序遍历
* @param root 根节点
*/
export function inorderTraversal(root: TreeNode | null) {
let res: number[] = [];
if (root) {
if (root.left) {
res = res.concat(inorderTraversal(root.left));
}
// 在遍历 right 节点之前 提交 val 就是中序遍历
res.push(root.val);
if (root.right) {
res = res.concat(inorderTraversal(root.right));
}
}
return res;
}
/**
* 二叉树的后序遍历
* @param root 根节点
*/
export function postorderTraversal(root: TreeNode | null) {
let res: number[] = [];
if (root) {
if (root.left) {
res = res.concat(postorderTraversal(root.left));
}
if (root.right) {
res = res.concat(postorderTraversal(root.right));
}
// 在遍历完所有节点之后 提交 val 就是后序遍历
res.push(root.val);
}
return res;
}
- 层序遍历，层序遍历需要我们了解一些多源 BFS 的思路，102. 二叉树的层序遍历 - 力扣（LeetCode）
/**
* 二叉树的层序遍历
* @param root 根节点
*/
export function levelOrder(root: TreeNode | null): number[][] {
// 最终结果的二维数组
const res: number[][] = [];
if (!root) return res;
// 暂存节点的队列, 也就是当前层的队列
const q: TreeNode[] = [root]; // 初始化时先将 root 添加进队列中
while (q.length) {
// 当前层的值数组
const curVal: number[] = [];
// 遍历当前层, 因为会动态操作 q 队列, 所以需要使用 for 循环
const { length } = q;
for (let i = 0; i < length; i++) {
// 此处不可能存在 q.shift() 返回 undefined 的情况
const cur = q.shift() as TreeNode;
// 提交当前节点的值
curVal.push(cur.val);
// 先提交left并使用使用shift即为从左到右的提交顺序
if (cur.left) q.push(cur.left);
if (cur.right) q.push(cur.right);
}
res.push(curVal);
}
return res;
}
二叉树的一些经典算法
没有实例的数据结构都是空洞且乏味的。
- 二叉树的最大深度
给定一个二叉树, 找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 同理可得计算"最深 DOM 节点树的深度"的实现。
LeetCode 地址：104. 二叉树的最大深度 - 力扣（LeetCode）
1.1 用递归实现
/**
* 求树的最大深度, 使用内部递归的方式
* @param root 根节点
*/
export function maxDepthUseTraverse(root: TreeNode | null): number {
let res = 0;
let depth = 0;
// 内部遍历框架
function traverse(node: TreeNode | null) {
if (!node) {
// 更新最大深度
res = Math.max(depth, res);
return;
}
// 入栈
depth++;
traverse(node.left);
traverse(node.right);
// 出栈
depth--;
}
traverse(root);
return res;
}
1.2 解决子问题方式实现
/**
* 求树的最大深度, 使用分解问题成计算左右子树高度的方式
* @param root 根节点
*/
export function maxDepthUseDecomposition(root: TreeNode | null): number {
if (!root) {
return 0;
}
// 获取左子树的最大深度
const leftMaxDepth = maxDepthUseDecomposition(root.left);
// 获取右子树的最大深度
const rightMaxDepth = maxDepthUseDecomposition(root.right);
// 比较它们并加上根节点
return Math.max(leftMaxDepth, rightMaxDepth) + 1;
}
PS: 计算最深 DOM 节点树的深度
/**
* 计算最深 DOM 节点树的深度
* @param root 根节点
*/
export function maxDepthForElement(root: Element): number {
if (!root.children.length) {
return 0;
}
// 比较它们并加上根节点
return Math.max(...[...root.children].map(children => maxDepthForElement(children))) + 1;
}
- 翻转二叉树
给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。
/**
* 226. 翻转二叉树
* @param root 根结点
*/
export function invertBinaryTree(root: TreeNode | null): TreeNode | null {
// 思路: BFS + 层序遍历
if (!root) return null;
// 层序遍历模版
const stack: TreeNode[] = [root];
while (stack.length) {
const node = stack.pop() as TreeNode;
const temp = node.right;
// 交换节点
node.right = node.left;
node.left = temp;
// 入栈
if (node.left) stack.push(node.left);
if (node.right) stack.push(node.right);
}
return root;
}
- 合并二叉树
给你两棵二叉树：root1 和 root2 合并它们，并返回合并后的二叉树。
/**
* 617. 合并二叉树
* @param root1 根节点1
* @param root2 根节点2
*/
export function mergeTwoBinaryTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
// 思路: DFS
// 取root1为基准合并root2
// 边界
if (!root1) return root2;
if (!root2) return root1;
const stack: [TreeNode, TreeNode][] = [[root1, root2]];
while (stack.length) {
const [r1, r2] = stack.pop() as [TreeNode, TreeNode];
r1.val += r2.val;
// 入栈
if (r1.left && r2.left) {
stack.push([r1.left, r2.left]);
}
if (r1.right && r2.right) {
stack.push([r1.right, r2.right]);
}
// 插入
if (!r1.left) {
r1.left = r2.left;
}
if (!r1.right) {
r1.right = r2.right;
}
}
return root1;
}
总结
慌慌张张，匆匆忙忙，为何生活总是这样～ 现在是 4 月末了，金三银四的浪潮只剩尾巴了，赶紧抓紧时间一起学习吧，共勉！