[剑指offer] 树的子结构

作者: 繁著 | 来源:发表于2018-06-29 14:45 被阅读0次

题目描述

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

解题思路

  • 递归思想,如果根节点相同则递归调用IsSubtree(),如果根节点不相同,则判断root1的左子树和roo2是否相同,再判断右子树和root2是否相同;
  • 注意节点为空的条件,HasSubTree中,只要有树为空就返回false; IsSubtree中,要先判断root2,如果root2为空,则说明第二棵树遍历完了,即匹配成功。

参考代码

/**
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) {
        if(root1 == null || root2 == null){
            return false;
        }
        return IsSubtree(root1, root2) || 
               HasSubtree(root1.left, root2) ||
               HasSubtree(root1.right, root2);
    }
    public boolean IsSubtree(TreeNode root1, TreeNode root2){
        //要先判断roo2, 不然{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}这个测试用例通不过。
        if(root2 == null)
            return true;
        if(root1 == null)
            return false;
        if(root1.val == root2.val){
            return IsSubtree(root1.left, root2.left) && 
                IsSubtree(root1.right, root2.right);
        }else
            return false;
    }
}

相关文章

  • 2022-04-30

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

  • [剑指offer] 树的子结构

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

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

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

  • 剑指offer——树的子结构

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

  • 剑指offer - 树的子结构

    题目 输入两棵二叉树A和B,判断B是不是A的子结构。二叉树节点的定义如下: 下图中的二棵二叉树,由于A中有一部分子...

  • [剑指Offer]树的子结构

    本文首发于我的个人博客Suixin’s Blog原文: https://suixinblog.cn/2019/03...

  • 【剑指Offer】017——树的子结构(树)

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

  • 剑指offer----树的子结构

    题目:输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构) 代码: isSu...

  • 【剑指Offer 18】树的子结构

    题目:输入两棵二叉树A和B,判断B是不是A的子结构。 代码如下: 来源:http://blog.csdn.net/...

  • 剑指offer之树的子结构

    树的子结构 欢迎关注作者简书csdn传送门 题目   输入两颗二叉树A和B,判断B是不是A的子结构 思想   要查...

网友评论

    本文标题:[剑指offer] 树的子结构

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