Lintcode245 Subtree solution 题解
发布在LINTCODE2018年2月22日view:237
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

You have two every large binary trees:T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

Notice:A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

有两个不同大小的二叉树:T1有上百万的节点;T2有好几百的节点。请设计一种算法,判定T2是否为T1的子树。

【注】若 T1 中存在从节点 n 开始的子树与 T2 相同,我们称 T2 是 T1 的子树。也就是说,如果在 T1 节点 n 处将树砍断,砍断的部分将与 T2 完全相同。

【题目链接】

http://www.lintcode.com/en/problem/subtree/

【题目解析】

判断 T2是否是 T1的子树,首先应该在 T1中找到 T2的根节点,找到根节点后,两棵子树必须完全相同。所以整个思路分为两步走:第一:找根节点,第二:判断两棵树是否全等。看起来很简单,但实际实现时还是细致一点,尤其要注意递归的先后顺序、条件与&条件或的处理。

【参考答案】

http://www.jiuzhang.com/solutions/subtree/

评论
发表评论
暂无评论
PUBLISHED IN

我的收藏