剑指offer-树的子结构

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

思路
在树A中找出和树B的根节点一样的节点
若有,判断树A中以R为根结点的子树是不是包含和树B一样的结构

递归遍历树,判断两个树的节点是否相同,结束条件:子树为空

Java

/**
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;
    }
    boolean result = false;
    if (root1.val == root2.val) {
      result = treeAHasTreeB(root1, root2);
    }
    if (!result)  // 如果没有相同的节点,继续向下找
      return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    else 
      return true;
  }
  public boolean treeAHasTreeB(TreeNode parent, TreeNode child) {
    if (child == null) {
      return true;
    } else if (parent == null) {
      return false;
    }
    if (parent.val != child.val) {
      return false;
    }
    return treeAHasTreeB(parent.left, child.left) && treeAHasTreeB(parent.right, child.right);
  }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目 输入两棵二叉树A和B,判断B是不是A的子结构。二叉树节点的定义如下: 下图中的二棵二叉树,由于A中有一部分子...
    Longshihua阅读 203评论 0 1
  • 题目描述 输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构) 解题思路 总...
    Mereder阅读 196评论 0 0
  • 题目描述 树的子结构 输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构) ...
    一只可爱的柠檬树阅读 112评论 0 0
  • 本文首发于我的个人博客Suixin’s Blog原文: https://suixinblog.cn/2019/03...
    Sui_Xin阅读 553评论 0 1
  • 题目描述 输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构) 解题思路 递...
    繁著阅读 353评论 0 0