剑指Offer

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

解题思路

首先判断 A 和 B 是否是空，如果为空，返回false；否则找到 A 和 B 的根结点相同的结点，然后依次比较。可以用递归的形式在 A 中找 B 的根结点。

实现

/*树结点定义*/ 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 = check(root1, root2); if (!result) result = HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2); return result; } private boolean check(TreeNode root1, TreeNode root2) { if (root1 == null && root2 == null) return true; else if (root2 == null) return true; else if (root1 == null) return false; if (root1.val == root2.val) return check(root1.left, root2.left) && check(root1.right, root2.right); return false; } }