题解 | #判断t1树是否包含t2树全部的拓扑结构#

代码如下

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Stack;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

class ScannerInfo {
    int rootNum;
    int[][] info;
    public ScannerInfo(int rootNum, int[][] info) {
        this.rootNum = rootNum;
        this.info = info;
    }
}

public class Main {
    static Map<Integer,TreeNode> cache = new HashMap<>(16);

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            ScannerInfo bigTreeScannerInfo = scannerInfo(scanner);
            TreeNode bigTree = constructTree(bigTreeScannerInfo.rootNum, bigTreeScannerInfo.info);
            ScannerInfo smallTreeScannerInfo = scannerInfo(scanner);
            TreeNode smallTree = constructTree(smallTreeScannerInfo.rootNum, smallTreeScannerInfo.info);
            System.out.printf("%s\n", String.valueOf(isSubTree(bigTree, smallTree)));
        }
    }

    private static boolean isSubTree(TreeNode big, TreeNode small) {
        boolean result1 = check(big, small);
        boolean result2 = check(big.left, small);
        boolean result3 = check(big.right,small);
        return result1 || result2 || result3;
    }

    private static boolean check(TreeNode big, TreeNode small) {
        if (small == null) {
            return true;
        }
        if (big == null) {
            return false;
        }
        if (big.val != small.val) {
            return check(big.left, small) || check(big.right,small);
        }
        return check(big.left, small.left) && check(big.right, small.right);
    }

    private static ScannerInfo scannerInfo(Scanner scanner) {
        int treeNum = scanner.nextInt();
        int treeRootNum = scanner.nextInt();
        int temp = treeNum;
        int i = 0;
        int[][] info = new int[treeNum][3];
        while(temp > 0) {
            info[i][0] = scanner.nextInt();
            info[i][1] = scanner.nextInt();
            info[i][2] = scanner.nextInt();
            i++;
            temp--;
        }
        ScannerInfo scannerInfo = new ScannerInfo(treeRootNum, info);
        return scannerInfo;
    }

    private static TreeNode constructTree(int rootNum, int[][] info) {
        cache = new HashMap<>();
        if (info == null || info.length == 0 || rootNum == 0) {
            return null;
        }
        for(int i = 0;i < info.length;i++) {
            TreeNode cur = getOrPutFromCache(info[i][0]);
            TreeNode left = getOrPutFromCache(info[i][1]);
            TreeNode right = getOrPutFromCache(info[i][2]);
            cur.left = left;
            cur.right = right;
        }
        return cache.get(rootNum);

    }

    private static TreeNode getOrPutFromCache(int num) {
        if (num == 0) {
            return null;
        }
        TreeNode result = cache.get(num);
        if (result == null) {
            result = new TreeNode(num);
            cache.put(num, result);
        }

        return result;
    }
}

把t1称为大树，t2称为小树，题目可以转化为在大树，大树的左子树，大树的右子树上寻找小树。
如果小树已经遍历到null，那么说明在大树中找到了小树，此时大树可能为空(完全相同的结构)，也可能不为空(小树只是大树的一部分)；如果发现大树遍历到了null，那么说明没找到小树，返回false；如果发现两者值不同，那么把大树分别移到左孩子和右孩子重复上述过程，只要大树的左右子树上有一颗找到即可，所以用||连接；如果发现两者值相同，那么就分别校验对应左右位置上的值是否正确，此时必须左右子树都相等方可返回true。