劍指offer - 樹的子結構

樹的子結構

• 題目描述
• 算法思路
• 代碼實作

題目描述

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

示例

輸入：{8,8,#,9,#,2,#,5},{8,9,#,2}
傳回值：true
           

算法思路

1. 首先，我們要在二叉樹A中找到跟二叉樹B根節點相等的值
2. 然後以此為節點，再遞歸判斷二叉樹A的左子樹和二叉樹B的左子樹是否相等，右子樹是否相等
3. 當左右子樹都相等時，說明二叉樹B是二叉樹A的子結構

代碼實作

/**
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) {
    	//有一個子樹為空，傳回false
        if(root1==null || root2==null) return false;
        return recur(root1,root2) //遞歸周遊左右子樹是否相等
            || HasSubtree(root1.left,root2) //root1的左節點是否跟root2根節點相等
            || HasSubtree(root1.right,root2);//root1的右節點是否跟root2根節點相等
    }
    
    //這個函數就是判斷二叉樹A和二叉樹B是否相等
    //這裡利用的是二叉樹的先序周遊
    private boolean recur(TreeNode root1,TreeNode root2){
        //節點2全部周遊完，傳回true
        if(root2==null) return true;
        if(root1==null || root1.val!=root2.val) return false;
        //隻有左右子樹相等時才傳回true
        return recur(root1.left,root2.left) && recur(root1.right,root2.right);
    }
}