面试题26. 树的子结构

最新推荐文章于 2024-07-05 19:21:03 发布

puspos

最新推荐文章于 2024-07-05 19:21:03 发布

阅读量134

点赞数

分类专栏：剑指offer medium

本文链接：https://blog.csdn.net/puspos/article/details/105257196

版权

medium 同时被 2 个专栏收录

116 篇文章

订阅专栏

剑指offer

45 篇文章

订阅专栏

问题
在这里插入图片描述

例子

在这里插入图片描述

思路
遍历树a，把a的子树结构和b进行比较
在这里插入图片描述
比较时，只要b进行到null，不管a进行到是不是null，返回true

方法1
$$

$$
方法2
$$

$$

代码

//方法1
class Solution {
    private boolean res = false;
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null || B==null) return false;
        inOrder(A,B);
        return res;
    }
    
    public void inOrder(TreeNode a, TreeNode b) {
        if(a.left!=null) inOrder(a.left,b);
        if(check(a,b)) res=true;
        if(a.right!=null) inOrder(a.right,b);
    }
    
    
    public boolean check(TreeNode a, TreeNode b) {
        // if(a==null && b==null || (b==null && a!=null)) return true;
        // if((a==null && b!=null) || a.val!=b.val) return false;
        if(b==null) return true;
        if(a==null || a.val!=b.val) return false;
        
        return check(a.left,b.left) && check(a.right,b.right);
    }
}
//方法2