1.题目

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

2.思路

一棵大树 A，一棵小树 B，若 B 是 A 的子树，则：
- B 和 A 的结点值完全相同，它们俩的左子树、右子树所有结点的值也完全相同
- 或者 B 的左孩子和 A 的结点值完全相同，它们俩的左子树、右子树所有结点的值也完全相同
- 或者 B 的右孩子和 A 的结点值完全相同，它们俩的左子树、右子树所有结点的值也完全相同

1573824157192

这棵大树的子树有：

4 和 5 对应的两棵子树
3 本身自己完整的一棵树

而里面的小框圈出来的不是 3 这棵大树的子树！

代码

public class Solution{
    public boolean HasSubtree(TreeNode root1, TreeNode root2){
        if(root1 == null|| root2 == null){
            return false;
        }
        return judgeSubTree(root1,root2) || judgeSubTree(root1.left,root2)                                  ||judgeSubTree(root1.right,root2);
    }
    private boolean judgeSubTree(TreeNode root1, TreeNode root2){
        if(root2 == null){
            return true;
        }
        if(root1 == null){
            return false;
        }
        if(root1.val != root2.val){
            return false;
        }
        return judeSubTree(root1.left,root2.left)&&
            judeSubTree(root1.right,root2.right);
    }
}

子结构

只需要找到其中的一部分

public class Solution{
    public boolean HasSubtree(TreeNode root1, TreeNode root2){
        if(root1 == null|| root2 == null){
            return false;
        }
        return judgeSubTree(root1,root2) || judgeSubTree(root1.left,root2)                                  ||judgeSubTree(root1.right,root2);
    }
    private boolean judgeSubTree(TreeNode root1, TreeNode root2){
        if(root2 == null){
            return true;
        }
        if(root1 == null){
            return false;
        }
        if(root1.val != root2.val){
            return judgeSubTree(root1.left, root2) ||
                   judgeSubTree(root1.right, root2);
        }
        return judeSubTree(root1.left,root2.left)&&
            judeSubTree(root1.right,root2.right);
    }
}

3.总结

本题主要考查代码的递归级遍历算法。