題目描述

輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個樹的子結(jié)構(gòu)）

示例1

輸入

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

返回值

true

思路：

１．　設(shè)計match函數(shù)來匹配在ａ樹中是否含有ｂ樹（此時ａ和ｂ的ｖａｌｕｅ值相等）；
２．　遍歷整個大樹，找到與root2的值相等的節(jié)點，并使用ｍａｔｃｈ函數(shù)。

match函數(shù)分析：

很明顯要使用遞歸。
遞歸的基本功能：
如果在ａ樹中發(fā)現(xiàn)一個節(jié)點的值不等于ｂ樹中對應(yīng)位置的值，則返回ｆａｌｓｅ：

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

遞歸終止條件：
（１）　如果b樹已經(jīng)遍歷完，還沒有返回ｆａｌｓｅ，那么說明b確實是ａ的子結(jié)構(gòu)；
（２）　如果在ｂ樹沒有遍歷完畢的基礎(chǔ)上，a樹已經(jīng)遍歷完畢，那么說明ｂ并不是ａ的子結(jié)構(gòu)。

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)); 
    }
}