• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

【剑指Offer题解:java】树的子结构

互联网 diligentman 4周前 (01-31) 14次浏览

文章目录

    • 题目
    • 分析
    • 代码

题目

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

分析

  1. 先序遍历树 A中的每个节点node1
  2. 判断树A中以node1为根节点的子树是否包含树B

终止条件

  • 当节点 node2为空:说明树B已匹配完成(越过叶子节点),因此返回 true
  • 当节点 node1 为空:说明已经越过树 A叶子节点,即匹配失败,返回 false
  • 当节点 node1和 node2 的值不同:说明匹配失败,返回 false

判断 A 和 B 的左子节点是否相等

判断 A 和 B 的右子节点是否相等

【剑指Offer题解:java】树的子结构

【剑指Offer题解:java】树的子结构

【剑指Offer题解:java】树的子结构

代码

public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) return false;
        return HasSubtree2(root1, root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
    }

    public boolean HasSubtree2(TreeNode node1, TreeNode node2) {
        if (node2 == null) return true;
        if (node1 == null || node1.val != node2.val) return false;//node2还不为空
        return HasSubtree2(node1.left, node2.left) && HasSubtree2(node1.right, node2.right);
    }


程序员灯塔
转载请注明原文链接:【剑指Offer题解:java】树的子结构
喜欢 (0)