首页 > 代码库 > 《剑指Offer》题目:树的子结构

《剑指Offer》题目:树的子结构

题目描述:树的子结构

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

题目分析:此题可以拆成两题,1.在二叉树中查找是否存在某个结点;2.判断两个二叉树是否有相同的结构

 

Java代码:

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }

}
public class HasSubtree {
    public boolean hasSubtree(TreeNode root1,TreeNode root2) {
        boolean res = false;
        if (root1 != null && root2 !=null){
            if (root1.val == root2.val){
                //这时候判断两个二叉树是否有相同的结构
                res = isAHasB(root1, root2);
            }
            if (!res){
                res = hasSubtree(root1.left,root2);
            }
            if (!res){
                res = hasSubtree(root1.right, root2);
            }
        }
        return res;
    }
   //判断两个二叉树是否有相同的结构
public boolean isAHasB(TreeNode root1,TreeNode root2){ if (root2 == null) return true; if (root1 == null) return false; if (root1.val != root2.val) return false; return isAHasB(root1.left, root2.left) && isAHasB(root1.right, root2.right); } }

 

《剑指Offer》题目:树的子结构