检查子树
难度:
标签:
题目描述
T1 and T2 are two very large binary trees. Create an algorithm to determine if T2 is a subtree of T1.
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.
Note: This problem is slightly different from the original problem.
Example1:
Input: t1 = [1, 2, 3], t2 = [2] Output: true
Example2:
Input: t1 = [1, null, 2, 4], t2 = [3, 2] Output: false
Note:
- The node numbers of both tree are in [0, 20000].
代码结果
运行时间: 48 ms, 内存: 23.1 MB
/*
* 使用Java Stream的方式实现检查T2是否为T1的子树
* 思路：
* 1. 转换树为字符串表示。
* 2. 检查T2的字符串表示是否是T1的子字符串。
*/
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Solution {
public boolean isSubtree(TreeNode t1, TreeNode t2) {
String t1Str = preOrder(t1).collect(Collectors.joining(","));
String t2Str = preOrder(t2).collect(Collectors.joining(","));
return t1Str.contains(t2Str);
}
private Stream<String> preOrder(TreeNode node) {
if (node == null) return Stream.of("#");
return Stream.concat(Stream.of(String.valueOf(node.val)),
Stream.concat(preOrder(node.left), preOrder(node.right)));
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}解释
方法:
此题解主要采用递归方法来确定T2是否为T1的子树。首先定义一个辅助函数isSameTree，用于判断两棵树是否完全相同。然后在主函数checkSubTree中，对T1进行递归遍历，在每个节点处调用isSameTree来检查该节点生成的子树是否与T2相同。如果在任何节点发现T2为子树，则立即返回true。如果遍历完整个树也没有发现，则返回false。
时间复杂度:
O(n*m)
空间复杂度:
O(log n) in best case, O(n) in worst case
代码细节讲解
🦆
在算法中，对于边界情况处理，如果T2为空树，算法是否默认T2为T1的子树，根据题目要求这样的处理是否合理？
▷🦆
在递归调用isSameTree时，如果T1的某个节点与T2的根节点值相同，但其子树结构不同，算法如何确保继续在T1中寻找可能的匹配位置？
▷🦆
在实现中，如果T1和T2的节点数极度不平衡，例如T1有几万个节点而T2只有几个节点，这种情况下是否有更优的遍历策略或优化方法可用以提高效率？
▷