树的子结构

￡神魔★判官ぃ 2022-03-25 15:26 163阅读 0赞

# [树的子结构][Link 1] #

## 题目描述 ##

输入两棵二叉树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都不为零的时候，才进行比较。否则直接返回false
    18         if (root2 != null && root1 != null) {
    19             //如果找到了对应Tree2的根节点的点
    20             if(root1.val == root2.val){
    21                 //以这个根节点为为起点判断是否包含Tree2
    22                 result = doesTree1HaveTree2(root1,root2);
    23             }
    24             //如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2
    25             if (!result) {
    26                 result = HasSubtree(root1.left,root2);
    27             }
    28              
    29             //如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2
    30             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已经遍历完了都能对应的上，返回true
    40         if (node2 == null) {
    41             return true;
    42         }
    43         //如果Tree2还没有遍历完，Tree1却遍历完了。返回false
    44         if (node1 == null) {
    45             return false;
    46         }
    47         //如果其中有一个点没有对应上，返回false
    48         if (node1.val != node2.val) {  
    49                 return false;
    50         }
    51          
    52         //如果根节点对应的上，那么就分别去子节点里面匹配
    53         return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);
    54     }}

posted @ 2018-08-08 09:11 [Octopus22][] 阅读( ...) 评论( ...) [编辑][Link 2] 收藏

[Link 1]: https://www.cnblogs.com/Octopus-22/p/9440801.html
[Octopus22]: https://www.cnblogs.com/Octopus-22/
[Link 2]: https://i.cnblogs.com/EditPosts.aspx?postid=9440801