本文共 587 字，大约阅读时间需要 1 分钟。
问题A：
判断一棵树里是否含有另一棵树的结构：遍历每个节点判断，时间复杂度O(N*M)
问题B：
找到二叉树中的最大搜索二叉子树： 树形dp，时间O(N)，空间O(h)递归处理，从下向上，每个节点记录其和其子树中最小值和最大值。
每个节点同时记录是否为搜索子树的根，然后不断合并。问题C：
找到二叉树中的最大搜索二叉树结构： 树形dp，时间O(N*h)，空间O(N)每个节点维护拓扑贡献记录(l,r)，分别代表左右子树对当前节点的贡献数量。
依然从下向上，每提高一次树高，更新子树对当前新根的拓扑贡献记录。拓扑贡献有个特点，若左子树根节点满足搜索关系，则左子树的左记录不需要改变，只需要判断左子树的右边界。同理，只需判断右子树的左边界。时间复杂度为O(N*h)
问题D：
打印所有和为某值的路径：
路径定义为根到叶节点。回溯，时间O(N*h)
问题E：
在二叉树中找到累加和为指定值的最长路径： 这里路径定义为从上到下的节点链。哈希+回溯，时间O(N)，空间O(h)
从上向下遍历，维护一个该路径上的哈希表
哈希表存储(sum,level),代表高度level上有和为sum的路径。
问题F：
判断t1树是否包含t2树全部拓扑结构：最优做法貌似就是暴力，时间O(N*M)
问题G：
判断t1树是否包含结构为t2的子树：二叉树序列化后kmp，时间O(N+M)
转载地址：http://pbwji.baihongyu.com/