牛客网-树的子结构

朱雀 2023-03-01 09:36 85阅读 0赞

# 题目描述 #

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

oj连接：  
[https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88][https_www.nowcoder.com_practice_6e196c44c7004d15b1610b9afca8bd88]

# 解法1 #

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        
        public boolean is(TreeNode root1,TreeNode root2){ 
                //root2等于null时，说明已经比较完了，就返回true
                if(root2 ==null)
                    return true;
                //root1等于null时，说明root2不是root1的子树，返回false
                if(root1 ==null)
                    return false;
                //如果root1和root2的值不一样，就返回false
                if(root1.val != root2.val)
                    return false;
                //如果一样，就继续比较root1和root2的左节点和右节点。
                return is(root1.left,root2.left) && is(root1.right,root2.right);
        }
        
        public boolean HasSubtree(TreeNode root1,TreeNode root2) { 
            //如果有一个为null，就直接返回false，因为空的树，不是任何一个树的子树
            if(root1 == null || root2 ==null)
                return false;
            
            boolean bool = false;
            
            //找到相等的一个，从相等的根节点处开始比较左右子节点
            if(root1.val == root2.val){ 
                bool = is(root1,root2);
            }
            
            //如果root1,val != root2.val 那么就继续寻找左右子节点
            if(bool != true)
                bool = HasSubtree(root1.left,root2);
            //如果还等于false，说明在left中没有找到，就继续找right
            if(bool != true)
                bool = HasSubtree(root1.right,root2);
            
            return bool;
            
        }
    }

[https_www.nowcoder.com_practice_6e196c44c7004d15b1610b9afca8bd88]: https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88