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