树的子结构

题目描述

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

解题思路

当 root1 和 root2 都不为空：

• 如果 root1=root2，判断 root2 是不是包含在 root1 内；
• 如果不在，对 root1.left 递归；
• 如果不在，对 root1.right 递归。

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