描述
给定彼此独立的两棵二叉树,树上的节点值两两不同,判断 t1 树是否有与 t2 树完全相同的子树。
示例1
输入:
{1,2,3,4,5,6,7,#,8,9},{2,4,5,#,8,9}
返回值:
true
备注:
1≤n≤500000
方法一:递归
要判断t2是否为t1的子树,那么就先在t1中找到t2的根节点,然后再进行遍历判断从当前节点的左右子树相不相同,如果一旦出现不同,那么立即返回false。
如果t2遍历完节点,t1也遍历完节点,则证明t2为t1的子树。
如果t1先遍历完节点,t2还没遍历完节点,那么则证明t2不是t1的子树。
public boolean isContains (TreeNode root1, TreeNode root2) {
// 如果当前节点为空,那么则t2不可能为t1的子树了
if(root1 == null)
return false;
// 递归寻找t1树中跟t2根节点相同的节点,即找到图中紫色圈的节点
/* 三种可能,1、当前节点的左节点跟t2根节点相同
2、当前节点的右节点跟t2根节点相同
3、当前节点跟t2根节点相同
*/
return isContains(root1.left,root2) || isContains(root1.right,root2)
|| check(root1,root2);
}
pub