1. 写树相关的算法,先搞清楚 root
节点【该做什么】以及【什么时候做】,然后根据函数定义递归调用子节点
【该做什么】就是想清楚到底如何实现才能实现题目的效果;
【什么时候做】就是思考这段代码到底应该放在前序/中序/后序代码位置上
2. 递归算法的关键明确函数的定义,相信这个定义,不要跳进递归细节。
3. 如何表示一颗二叉树
3.1 用前序、中序或者后序序列化二叉树,注意左、右子树之间需要有分隔符,这里主要考虑避免出现不同的树,序列化后结果相同的情况。举例说明,如果节点之间不加分割符会出现这么一种情况,[2, 11, 3]
和[2, 1, 13]
不同的二叉树,序列化之后结果相同的情况
string SeqSubtrees(TreeNode* root){
if(root == nullptr){
return "#";
}
string left = SeqSubtrees(root->left);
string right = SeqSubtrees(root->right);
# "," 逗号不能省略
string cur_seq = left + "," + right + "," + to_string(root->val);
return cur_seq;
}
3.2 如何完成二叉树的序列化|反序列化
一般语境下,单前序遍历结果是不能还原二叉树结构的,因为缺少空指针的信息,至少需要得到前、中、后序遍历中的两种才能还原二叉树。但是包含全部空指针信息的序列化结果是可以反序列化出原二叉树的
举例:297. 二叉树的序列化与反序列化
4. 二叉搜索树(BST)
BST相关的问题,要么利用BST左小右大的特性提升算法效率,要么利用中序遍历的特性满足题目需求
5. 深入思考下前、中、后序的执行顺序
不是3个节点的顺序,而是整颗树时的执行顺序