树的子结构Java-剑指offer

亦凉 2024-04-17 17:27 40阅读 0赞

## 题目描述 ##

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

## 解题思路 ##

1、比较根节点val相同，则进行左右节点的比较：（如果b为空了，那直接输出true。如果a为空，b不为空，则输出false;

如果两者不为null，比较节点值，再进行比较左右节点）；

2、如果根节点val不同，则进行比较a的根节点的左节点，递归比较；

3、如果根节点val不同，并且左节点不同，则进行比较a的根节点的右节点，递归比较；

源码：

> 1.  /\*\*
> 2.  public class TreeNode \{
> 3.      int val = 0;
> 4.      TreeNode left = null;
> 5.      TreeNode right = null;
> 6.      public TreeNode(int val) \{
> 7.          this.val = val;
> 8.      \}
> 9.  \}
> 10. \*/
> 11. public class Solution \{
> 12.     public boolean HasSubtree(TreeNode root1,TreeNode root2) \{
> 13.         boolean result = false; //设置结果值进行存储
> 14.         if(root1 == null || root2 == null) return false;
> 15.        // if(root1.val == root2.val || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2))
> 16.        if(root1.val == root2.val)//如果根节点值相等，则进行左右
> 17.         \{
> 18.             result = isSubtree(root1,root2);
> 19.         \}
> 20.         if(!result)
> 21.         \{
> 22.           result = HasSubtree(root1.left, root2);
> 23.         \}
> 24.          if(!result)
> 25.         \{
> 26.           result = HasSubtree(root1.right, root2);
> 27.         \}
> 28.         return result;
> 29.     \}
> 30.      public boolean isSubtree(TreeNode root1,TreeNode root2) \{
> 31.         if(root2 == null)
> 32.             return true;
> 33.         if(root1 == null)
> 34.             return false;
> 35.        if(root1.val != root2.val)
> 36.            return false;
> 37.        return  (isSubtree(root1.left,root2.left) && isSubtree(root1.right,root2.right));
> 38.     \}
> 39. \}