题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）     题目链接： https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&&tqId=11170&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking  

分析：

判断B是不是A的子结构，也就是从 A的任何一个节点开始判断是否包含了B。

父节点判断是否值是否相等：

相等：

(judge(root1.left,root2.left) && judge(root1.right,root2.right))||不相等;

不相等：

judge(root1.left,root2)||judge(root1.right,root2);

父节点相等的情况增加一个判断左子树和右子树是否相等的判断，如果全部相等，说明是子结构，返回true。

如果左子树和右子树中有一个不相等，则不是子结构，返回false，然后再走当前父节点的不相等的情况。

 

 

 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 boolean HasSubtree(TreeNode root1,TreeNode root2) {
16         //处理tree2是null情况
17         if(root2==null){
18             return false;
19         }
20         return judge(root1,root2);
21     }
22     
23     public boolean judge(TreeNode root1,TreeNode root2){
24         //说明tree2遍历结束，返回true
25         if(root2 == null){
26             return true;
27         }
28         //tree1节点为null，而tree2不为null，说明这个节点处不匹配，返回false
29         if(root1 == null && root2 != null){
30             return false;
31         }
32         //tree1与tree2节点值相等情况
33         if(root1.val == root2.val){
34             //1、判断他们的左子树和右子树是否相等  2、判断tree1左子树与tree2是否相等  3、判断tree1右子树与tree2是否相等
35             return (judge(root1.left,root2.left) && judge(root1.right,root2.right))||judge(root1.left,root2)||judge(root1.right,root2);
36         }
37         //tree1与tree2节点值不相等情况
38         // 2、判断tree1左子树与tree2是否相等  3、判断tree1右子树与tree2是否相等
39         return judge(root1.left,root2)||judge(root1.right,root2);
40     }
41 }