本文共 1810 字，大约阅读时间需要 6 分钟。

1. 本题知识点

树

2. 题目描述

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

例如：

二叉树 A：    	    8    	   /  \    	  6   10    	 / \  / \    	5  7 9  11二叉树 B：    	  6      	 / \     	5  7

3. 解题思路

可以分两步解决这个问题：

1. 遍历二叉树 A，在二叉树 A 中找到与二叉树 B 的根结点值相等的结点
2. 判断二叉树 B 是不是该结点的子树

4. 代码

public class TreeNode {
       int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {
           this.val = val;    }}

public class Solution {
       /**     * 输入两棵二叉树 A，B，判断 B 是不是 A 的子结构     * @param root1 二叉树 A     * @param root2 二叉树 B     * @return     */    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
           boolean result = false;        // 当两棵树都不为空时，才进行比较        if (root1 != null && root2 != null) {
               // 如果找到了与二叉树 B 的根结点值相等的结点            if (root1.val == root2.val) {
                   // 判断二叉树 B 是不是该结点的子树                result = IsSubtree(root1, root2);            }            // 如果没找到，遍历二叉树 A 的左结点            if (!result) {
                   result = HasSubtree(root1.left, root2);            }            // 如果还没找到，遍历二叉树 A 的右结点            if (!result) {
                   result = HasSubtree(root1.right, root2);            }        }        return result;    }    /**     * 判断二叉树 B 是不是该结点的子树     * @param root1 该结点     * @param root2 二叉树 B     * @return     */    public boolean IsSubtree(TreeNode root1, TreeNode root2) {
           // 二叉树 B 遍历完了，则说明是该结点的子树，返回 true        if (root2 == null) {
               return true;        }        // 二叉树 B 没遍历完，该结点却遍历完了，返回 false        if (root1 == null) {
               return false;        }        // 两棵树结点值不相同，返回 false        if (root1.val != root2.val) {
               return false;        }        // 继续判断两棵树子结点是否匹配        return IsSubtree(root1.left, root2.left) && IsSubtree(root1.right, root2.right);    }}

转载地址：http://cyjvb.baihongyu.com/