剑指Offer 26 树的子结构

mario 2020年09月15日 68次浏览

前言

做了一个小时没做出来,参考题解。

分析题目

image.png

题目让判断树A中是否包含树B,我理所应当的想到首先要找出树B的头在树A中的位置,以该结点为头,判断该树是否包含树B,于是,当发现A中有重复的结点时,我头大了,遂考虑参考题解。

解法

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
	//当||左边为真时会阻断,即右边的语句不会再执行
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {//比较A树是否包含B树
        if(B == null) return true;
        if(A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);//先序遍历
    }
}

参考

面试题26. 树的子结构(先序遍历 + 包含判断,清晰图解)