java判断一棵二叉树是另一棵二叉树的子树

àì夳堔傛蜴生んèń 2024-03-16 10:51 100阅读 0赞

## 判断一棵二叉树是另一棵二叉树的子树 ##

### 题目描述 ###

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。  
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

### 示例 ###

![在这里插入图片描述][60fcc79d2d294daf95acc2bba92ea4b4.png]  
![在这里插入图片描述][c092dc6a65d8400c84c05997db030379.png]

### 原题OJ链接 ###

https://leetcode.cn/problems/subtree-of-another-tree/

### 解答代码 ###

/**
     * 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 isSubtree(TreeNode root, TreeNode subRoot) {
        
            if(isSameTree(root,subRoot)){
        
                return true;
            }
            if(root == null || subRoot == null){
        
                return false;
            }
            if(isSubtree(root.right,subRoot) || isSubtree(root.left,subRoot)){
        
                return true;
            }
            return false;
        }
        public boolean isSameTree(TreeNode p, TreeNode q) {
        //判断两棵树是否完全相同
            if(p == null && q == null){
        
                return true;
            }
            if(p != null && q == null || p == null && q != null){
        
                return false;
            }
            if(p.val != q.val){
        
                return false;
            }
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }
    }

[60fcc79d2d294daf95acc2bba92ea4b4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/49493bb28e354343b503ff58ad45253e.png
[c092dc6a65d8400c84c05997db030379.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/e4c4ef43dc3c428d9552d9a779b4771f.png