题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
解题思路
1，首先判断根节点是否相等
2，如果根节点相等，在接着判断其子结构是否相等
3，显然是两个递归，第一个用于发现相等的根节点，第二个用于判断子结构是否相等。
代码实现
/** * */ package offerTest; /** * <p> * Title:HasSubtree * </p> * <p> * Description: * </p> * * @author 田茂林 * @data 2017年8月20日 下午8:33:03 */ public class HasSubtree { public boolean HasSubtrees(TreeNode root1, TreeNode root2) { boolean result = false; if (root1 != null && root2 != null) { if (root1.val == root2.val) { // 根节点相同 result = helper(root1, root2); // 根节点相同,如果子结构也相同，返回true，否则仍然是false } if (!result) { //如果是false，继续从左右子树寻找相同的 result = HasSubtrees(root1.left, root2)||HasSubtrees(root1.right, root2); } } return result; } // 判断子结构是否相同 public boolean helper(TreeNode root1, TreeNode root2) { if (root2 == null) return true; // 如果2为空，则说明树2已结递归调用完了，都符合 if (root1 == null) return false; // 如果2不为空，1为空则说明不符合 if (root1.val != root2.val) return false; return helper(root1.left, root2.left) && helper(root1.right, root2.right); } public static void main(String[] args) { // TODO Auto-generated method stub } }
