【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 的对象进行引用，必须特判它为空的情形// 待查找的树已经为空，无法进一步匹配，结果应该是 falseif(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);}
}