题目描述
给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例
给定的树 s:
3
/ \
4 5
/ \
1 2
给定的树 t:
4
/ \
1 2
返回 true,因为 t 与 s 的一个子树拥有相同的结构和节点值。
思路
1.递归比较两个数的结构。
2.比较A树和B树当前的结点,若A树和B树的值相等,则继续比较它们的左右子树;若不相等,则拿A树的左子树和右子树进行同样的过程。
3.当A树和B树同时遍历到了空结点,说明B是A的子结构;否则不是A的子结构。
Java代码实现
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if(s == null && t != null){
return false;
}
boolean flag = judgeTree(s,t);
if(!flag){
flag = isSubtree(s.left,t);
}
if(!flag){
flag = isSubtree(s.right,t);
}
return flag;
}
private boolean judgeTree(TreeNode s, TreeNode t){
if(s == null && t == null){
return true;
}
if(s != null && t == null){
return false;
}
if(s == null && t != null){
return false;
}
if(s.val != t.val){
return false;
}
return judgeTree(s.left,t.left) && judgeTree(s.right,t.right);
}
}
Golang代码实现
func isSubtree(s *TreeNode, t *TreeNode) bool {
if s == nil && t != nil{
return false
}
flag := judgeTree(s,t)
if !flag{
flag = isSubtree(s.Left,t)
}
if !flag{
flag = isSubtree(s.Right,t)
}
return flag
}
func judgeTree(s *TreeNode, t *TreeNode) bool {
if s == nil && t != nil{
return false
}
if s != nil && t == nil{
return false
}
if s == nil && t == nil{
return true
}
if s.Val != t.Val {
return false
}
return judgeTree(s.Left,t.Left) && judgeTree(s.Right,t.Right)
}
有疑问加站长微信联系(非本文作者)