美文网首页
剑指 Offer 26 树的子结构

剑指 Offer 26 树的子结构

作者: itbird01 | 来源:发表于2022-01-11 07:06 被阅读0次
题目.png

题意:输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构, 即 A中有出现和B相同的结构和节点值。

解题思路

解法1:
1.分析题意,存在三种情况,B是A的左子树的子树,B是A的右子树的子树,B是A的子树
2.由上分析,可知重点在于,如何判定B为A的子树:在A中遍历,如果找到a.val==b.val,此时开始遍历B,如果B遍历到叶子节点,则为A的子树

解题遇到的问题

后续需要总结学习的知识点

##解法1
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }

        return dfs(A, B) || isSubStructure(A.left, B)
                || isSubStructure(A.right, B);
    }

    private boolean dfs(TreeNode a, TreeNode b) {
        if (b == null) {
            return true;
        }

        if (a == null) {
            return false;
        }

        return a.val == b.val && dfs(a.left, b.left) && dfs(a.right, b.right);
    }

}

相关文章

  • 2022-04-30

    剑指 Offer 26. 树的子结构[https://leetcode.cn/problems/shu-de-zi...

  • 剑指 Offer 26 树的子结构

    题意:输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)B是A的子结构, 即 A中有...

  • 《剑指Offer》-26.树的子结构

    题干 输入两棵二叉树A和B,判断B是不是A的子结构。二叉树节点定义如下: 二叉树A 二叉树B 解题思路 获取B的根...

  • 剑指 Offer 26. 树的子结构

    主要思路:先用dfs来比较以root1和root2为头节点的子树能不能符合题意,如果不能再去递归引入root1.l...

  • 剑指 Offer 26. 树的子结构

    题目 输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)B是A的子结构, 即 A中有...

  • [剑指offer-26]树的子结构

    题目描述输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构) 解法 首先,约...

  • 剑指 Offer 26. 树的子结构

    给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值...

  • 剑指 Offer 26. 树的子结构

    输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构, 即 A中有出现...

  • [剑指offer] 树的子结构

    题目描述 输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构) 解题思路 递...

  • 【剑指 offer】树的子结构。

    1、题目描述 输入两棵二叉树A,B,判断B是不是A的子结构。 我们规定空树不是任何树的子结构。 样例树A8/ \...

网友评论

      本文标题:剑指 Offer 26 树的子结构

      本文链接:https://www.haomeiwen.com/subject/qfrvqrtx.html