树的子结构

题目描述

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

示例1

输入

{8,8,#,9,#,2,#,5},{8,9,#,2}

返回值

true

思路：

１．　设计match函数来匹配在ａ树中是否含有ｂ树（此时ａ和ｂ的ｖａｌｕｅ值相等）；
２．　遍历整个大树，找到与root2的值相等的节点，并使用ｍａｔｃｈ函数。

match函数分析：

很明显要使用递归。
递归的基本功能：
如果在ａ树中发现一个节点的值不等于ｂ树中对应位置的值，则返回ｆａｌｓｅ：

        if(a.val != b.val){
            return false;
        }

递归终止条件：
（１）　如果b树已经遍历完，还没有返回ｆａｌｓｅ，那么说明b确实是ａ的子结构；
（２）　如果在ｂ树没有遍历完毕的基础上，a树已经遍历完毕，那么说明ｂ并不是ａ的子结构。

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1 == null || root2 ==null){
            return false;
        }
        
        return match(root1,root2) || HasSubtree(root1.left,root2)|| HasSubtree(root1.right,root2);
    }

    boolean match(TreeNode a, TreeNode b){
        if(b == null){
            return true;
        }
        if(a == null){
            return false;
        }
        if(a.val != b.val){
            return false;
        }
            return (match(a.left,b.left) && match(a.right,b.right)); 
    }
}