知乎每日精选
·
数据结构-树及相关算法
💡
原文中文，约13200字，阅读约需32分钟。
📝
内容提要
二叉树是递归算法的关键，需要明确函数的定义和递归细节。二叉树的算法题基于递归框架，需要根据题目要求选择前序、中序或后序的递归框架。难点在于思考每个节点需要做什么，需要多刷题练习。
🎯
关键要点
- 二叉树是递归算法的关键，需要明确函数的定义。
- 写二叉树的算法题基于递归框架，需选择前序、中序或后序的递归框架。
- 难点在于思考每个节点需要做什么，需要多刷题练习。
- 前序遍历：先输出父节点，再遍历左子树和右子树。
- 中序遍历：先遍历左子树，再输出父节点，再遍历右子树。
- 后序遍历：先遍历左子树，再遍历右子树，最后输出父节点。
- 镜像翻转二叉树的函数定义是翻转节点的左右子节点。
- 辅助函数用于连接两个节点，采用前序遍历。
- 将二叉树拉平成链表的函数定义需要后序遍历。
- 构建最大二叉树的函数通过前序遍历实现。
- 通过前序和中序数组找到根节点的辅助函数。
- 通过后序和中序数组找到根节点的辅助函数。
- 获取重复子树的方法是通过后序遍历获取所有子树并序列化。
- 计算二叉树的总节点数有三种方法，分别适用于普通、满和完全二叉树。
- 二叉搜索树的中序遍历结果是有序的，需验证节点是否符合BST性质。
- 删除节点分为三种情况，需处理不同的子树结构。
- 二叉树的序列化和反序列化可以通过前序遍历、后序遍历和层级遍历实现。
- 赫夫曼树是带权路径长度最短的树，权值较大的节点离根较近。
- 赫夫曼编码是一种数据压缩算法，压缩率在20%-90%之间。
➡️
