判断t2树是否为t1树的子树
(牛客网—牛客题霸算法篇—NC98)
题目描述
给定彼此独立的两棵二叉树,树上的节点值两两不同,判断 t1 树是否有与 t2 树完全相同的子树。
思路
Java实现
递归
要判断t2是否为t1的子树,那么就先在t1中找到t2的根节点,然后再进行遍历。
判断从当前节点的左右子树相不相同,如果一旦出现不同,那么立即返回false。
如果t2遍历完节点,t1也遍历完节点,则证明t2为t1的子树。
如果t1先遍历完节点,t2还没遍历完节点,那么则证明t2不是t1的子树。
在isContains()方法中使用递归方法在t1树中寻找与t2树的根节点相同的节点,有三种可能:
1、当前节点的左节点跟t2根节点相同
2、当前节点的右节点跟t2根节点相同
3、当前节点跟t2根节点相同
找到与根节点相同的之后,调用check()方法,递归检查t1树从当前节点开始是否与t2树相同,如果t1先遍历完节点,t2还没遍历完节点,那么则证明t2不是t1的子树; 如果t2遍历完节点,t1没遍历完节点,则证明t2不是t1的子树;如果两者节点值不相同,那么证明t2不是t1的子树。
代码实现
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
public boolean check(TreeNode root1, TreeNode root2){
if(root1==null&&root2==null)
return true;
if(root1==null||root2==null||root1.val!=root2.val)
return false;
return check(root1.left,root2.left)&&check(root1.right,root2.right);
}
public boolean isContains (TreeNode root1, TreeNode root2) {
// write code here
if(root1==null)
return false;
return isContains(root1.left,root2)||isContains(root1.right,root2)||check(root1,root2);
}
}