Subtree
Description:
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.
T2 is a subtree of T1 in the following case:
1 3 / \ / T1 = 2 3 T2 = 4 / 4
T2 isn’t a subtree of T1 in the following case:
1 3 / \ \ T1 = 2 3 T2 = 4 / 4
分析:
判断T2
是否是T1
的子树,首先应该在T1
中找到T2
的根节点,且两棵子树必须完全相同。所以整个思路分为两步走:找根节点,判断两棵树是否全等;若不等,则需要判断是否是左/右子树的子树。
注意递归的先后顺序:需要先调用identical
(调用.val
前需要判断是否为null
),再递归调用isSubtree
判断左/右子树的情况。
identical
的调用,时间复杂度近似O(n)
, 查根节点的时间复杂度随机平均为O(m)
, 故总的时间复杂度可近似为O(mn)
。
代码如下:
1 | /** |