判断t2树是否为t1树的子树(Java)

判断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);
    }
}
上一篇:关于startup启动找不到相应文件问题-ORA-01078: failure in processing system parameters


下一篇:treevalue——Master Nested Data Like Tensor