题解 | #树的子结构#

题目

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

思路

本题的解法其实是模仿他人的。root1或者root2为空，都会返回false，如果均不为空，则遍历它们，如果当前结点的值相等，还需要遍历左右结点的值，判断是否相等，如果root2为空则返回true；如果root1为空则返回false；如果两个结点值不相等返回false；否则继续遍历判断左右结点是否和root2的左右结点的值是否一致。

挺不错的，自己没想出来，每种情况都考虑得很全面。

代码

/**
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) {
        /*if(root1 == null || root2 == null){
            return false;
        }else{
            return HasSubtree(root1,root2) || 
                HasSubtree(root1.left,root2) || 
                HasSubtree(root1.right,root2);
        }*/
        if(root1==null||root2==null) return false;
        boolean result=false;
        if(root1.val==root2.val){
            result = HashSubtreeHelper(root1,root2);
        }
        if(!result) result = HasSubtree(root1.left,root2);
        if(!result) result = HasSubtree(root1.right,root2);
        return result;
    }

    public boolean HashSubtreeHelper(TreeNode  root1,TreeNode root2){
        if(root2==null) return true;
        if(root1==null) return false;
        if(root1.val!=root2.val) return false;
        return HashSubtreeHelper(root1.left,root2.left)&&HashSubtreeHelper(root1.right,root2.right);
    }
}