【Leetcode 每日一题 - 扩展】面试题 04.10. 检查子树

问题背景

检查子树。
你有两棵非常大的二叉树：$T_1$，有几万个节点；$T_2$，有几万个节点。
设计一个算法，判断 $T_2$ 是否为 $T_1$ 的子树。
如果 $T_1$ 有这么一个节点，其子树与 $T_2$ 一模一样，则 $T_2$ 为 $T_1$ 的子树，也就是说，从此处把树砍断，得到的树与 $T_2$ 完全相同。

数据约束

• 两棵树上的节点数目都在范围 $[0,100]$ 内
• $-10^4\le Node.val\le 10^4$

解题过程

在节点上判断两棵树是否是 相同的树，递归检查所有节点即可。

具体实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean checkSubTree(TreeNode t1, TreeNode t2) {
        // 底下要用对 t1 的对象进行引用，必须特判它为空的情形
        // 待查找的树已经为空，无法进一步匹配，结果应该是 false
        if(t1 == null) {
            return false;
        }
        // 当前节点上两树是同一棵树的情况下，递归判断左右子树
        return isSameTree(t1, t2) || checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2);
    }

    // Leetcode 100.相同的树
    private boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null || q == null) {
            return p == q;
        }
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}