3
#yyds干货盘点# LeetCode程序员面试金典：检查子树
source link: https://blog.51cto.com/u_13321676/5969612
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# LeetCode程序员面试金典：检查子树
精选 原创检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。
如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。
注意：此题相对书上原题略有改动。
输入：t1 = [1, 2, 3], t2 = [2]
输出：true
输出：true
输入：t1 = [1, null, 2, 4], t2 = [3, 2]
输出：false
输出：false
代码实现：
class Solution {
public boolean checkSubTree(TreeNode t1, TreeNode t2) {
StringBuilder str1 = subsequence(t1);
StringBuilder str2 = subsequence(t2);
return str1.indexOf(str2.toString())!=-1;
}
public StringBuilder subsequence(TreeNode root){
StringBuilder str=new StringBuilder();
Deque<TreeNode> stack=new LinkedList<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode pop = stack.pop();
if(pop==null){
str.append("x");
continue;
}
str.append(pop.val);
stack.push(pop.right);
stack.push(pop.left);
}
return str;
}
}
public boolean checkSubTree(TreeNode t1, TreeNode t2) {
StringBuilder str1 = subsequence(t1);
StringBuilder str2 = subsequence(t2);
return str1.indexOf(str2.toString())!=-1;
}
public StringBuilder subsequence(TreeNode root){
StringBuilder str=new StringBuilder();
Deque<TreeNode> stack=new LinkedList<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode pop = stack.pop();
if(pop==null){
str.append("x");
continue;
}
str.append(pop.val);
stack.push(pop.right);
stack.push(pop.left);
}
return str;
}
}
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK