《剑指Offer》17树的子结构
题目：
输入两棵二叉树A和B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
过去提交通过的代码：
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) { boolean result=false; if(root1!=null&&root2!=null) { if(root1.val==root2.val) { result=DoesRoot1HaveRoot2(root1,root2); } if(!result) { result=HasSubtree(root1.left,root2); } if(!result) { result=HasSubtree(root1.right,root2); } } return result;
} boolean DoesRoot1HaveRoot2(TreeNode pRoot1,TreeNode pRoot2) { if(pRoot2==null) { return true; } if(pRoot1==null) { return false; } if(pRoot1.val!=pRoot2.val) { return false; } return DoesRoot1HaveRoot2(pRoot1.left,pRoot2.left)&&DoesRoot1HaveRoot2(pRoot1.right,pRoot2.right); }
}
再写一次：
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution { public boolean HasSubtree(TreeNode root1,TreeNode root2) { boolean res=false; if (root1!=null&&root2!=null) { if (root1.val==root2.val) { res=DoesRootHaveRoot2(root1,root2); } if (!res) { res=DoesRootHaveRoot2(root1.left,root2); } if (!res) { res=DoesRootHaveRoot2(root1.right,root2); } } return res; } public boolean DoesRootHaveRoot2(TreeNode pRoot1,TreeNode pRoot2) { if (pRoot2==null) { return true; } if (pRoot1==null) { return false; } if (pRoot1.val!=pRoot2.val) { return false; } return DoesRootHaveRoot2(pRoot1.left,pRoot2.left)&&DoesRootHaveRoot2(pRoot1.right,pRoot2.right); }
}
