树的子结构

题目描述

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

思路

第一种思路

利用递归来找子树，首先判断根节点是否一样，如果跟节点一样，我们继续根据两个树的左右子树去对比，如果B的左右子树完全可以被A的左右子树包含，那么我们就认为B树就是A树的子结构。
如果从根节点不相等，那么我们就拿A树的左子树或者A树的右子树与B做判断，判断步骤与之前类似，如果没有相对应的那么我们认为B树不是A树的子结构，如果返回true那么就认为B树为A树的子结构。

第二种思路

进行层级遍历，对A进行层级遍历，对B进行层级遍历，如果A中包含B，也就是B是A的子字符串，那么B就是A的子结构。
这种方法不行，因为右情况是不能这么辨别的，虽然这种方法不行，但是我们可以作为一种思路，保留下来，以后扩宽思路。

代码

第一种思路

public class Main {
    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(8);
        TreeNode treeNode1 = new TreeNode(9);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(9);
        TreeNode treeNode4 = new TreeNode(2);
        TreeNode treeNode5 = new TreeNode(4);
        TreeNode treeNode6 = new TreeNode(7);
        root1.left =treeNode1;
        root1.right = treeNode2;
        treeNode1.left = treeNode3;
        treeNode1.right = treeNode4;
        treeNode4.left = treeNode5;
        treeNode4.right = treeNode6;
        TreeNode root2 = new TreeNode(8);
        TreeNode root2TreeNode1 = new TreeNode(9);
        TreeNode root2TreeNode2 = new TreeNode(2);
        root2.left = root2TreeNode1;
        root2.right = root2TreeNode2;
        System.out.print(HasSubtree(root1,root2));
    }
    public static boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean result = false;
        //当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回false
        if (root2 != null && root1 != null) {
            //如果找到了对应Tree2的根节点的点
            if(root1.val == root2.val){
                //以这个根节点为为起点判断是否包含Tree2
                result = doesTree1HaveTree2(root1,root2);
            }
            //如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2
            if (!result) {
                result = HasSubtree(root1.left,root2);
            }

            //如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2
            if (!result) {
                result = HasSubtree(root1.right,root2);
            }
        }
        //返回结果
        return result;
    }

    public static boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {
        //如果Tree2已经遍历完了都能对应的上，返回true
        if (node2 == null) {
            return true;
        }
        //如果Tree2还没有遍历完，Tree1却遍历完了。返回false
        if (node1 == null) {
            return false;
        }
        //如果其中有一个点没有对应上，返回false
        if (node1.val != node2.val) {
            return false;
        }

        //如果根节点对应的上，那么就分别去子节点里面匹配
        return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);
    }

}
class TreeNode {
 int val = 0;
 TreeNode left = null;
 TreeNode right = null;

 public TreeNode(int val) {
 this.val = val;

 }
 }

第二种思路

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(8);
        TreeNode treeNode1 = new TreeNode(8);
        TreeNode treeNode2 = new TreeNode(7);
        TreeNode treeNode3 = new TreeNode(9);
        TreeNode treeNode4 = new TreeNode(2);
        TreeNode treeNode5 = new TreeNode(4);
        TreeNode treeNode6 = new TreeNode(7);
        root1.left =treeNode1;
        root1.right = treeNode2;
        treeNode1.left = treeNode3;
        treeNode1.right = treeNode4;
        treeNode4.left = treeNode5;
        treeNode4.right = treeNode6;
        TreeNode root2 = new TreeNode(8);
        TreeNode root2TreeNode1 = new TreeNode(9);
        TreeNode root2TreeNode2 = new TreeNode(2);
        root2.left = root2TreeNode1;
        root2.right = root2TreeNode2;
        System.out.print(HasSubtree(root1,root2));
    }
    public static boolean HasSubtree(TreeNode root1,TreeNode root2) {
        String root1str = Sequence(root1).toString();
        String root2str = Sequence(root2).toString();
        if(root1str.contains(root2str))
        {
            return true;
        }
        else return false;
    }
    private static StringBuilder Sequence(TreeNode root)
    {
        StringBuilder sb = new StringBuilder();
        if(root!=null)
        {
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);
            while (!q.isEmpty())
            {
                root = q.poll();
                sb.append(root.val);
                if(root.left!=null)
                {
                    q.offer(root.left);
                }
                if(root.right!=null)
                {
                    q.offer(root.right);
                }
            }
        }
        return sb;
    }
}
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}