题目描述

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

 

思路分析：

 

判定情况：

  1：比较根的值，若相等一直比较下去

  2：若根值不等，则比较A的左孩子和B的根

  3：若根值和左孩子不等，则比较A的右孩子和B的根

 

比较方法：

 1：若此时B为空，则说明B至少有一个匹配成功，返回TRUE

 2：若A为空，则说明A的结点小于B的结点数，false

 3：如果根节点对应上的话，递归下去，将A.left和B.left   A.right和B.right进行比较

 4：若A.val！=B.val ，返回flase

 

1 /** 2 public class TreeNode { 3     int val = 0; 4     TreeNode left = null; 5     TreeNode right = null; 6  7     public TreeNode(int val) { 8         this.val = val; 9 10     }11 12 }13 */14 public class Solution {15     public static boolean HasSubtree(TreeNode root1, TreeNode root2) {16         boolean result = false;17         //当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回false18         if (root2 != null && root1 != null) {19             //如果找到了对应Tree2的根节点的点20             if(root1.val == root2.val){21                 //以这个根节点为为起点判断是否包含Tree222                 result = doesTree1HaveTree2(root1,root2);23             }24             //如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree225             if (!result) {26                 result = HasSubtree(root1.left,root2);27             }28              29             //如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree230             if (!result) {31                 result = HasSubtree(root1.right,root2);32                }33             }34             //返回结果35         return result;36     }37  38     public static boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {39         //如果Tree2已经遍历完了都能对应的上，返回true40         if (node2 == null) {41             return true;42         }43         //如果Tree2还没有遍历完，Tree1却遍历完了。返回false44         if (node1 == null) {45             return false;46         }47         //如果其中有一个点没有对应上，返回false48         if (node1.val != node2.val) {  49                 return false;50         }51          52         //如果根节点对应的上，那么就分别去子节点里面匹配53         return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);54     }}