牛客网刷题——二叉树

雨点打透心脏的1/2处 2023-10-10 15:07 18阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：敲代码の流川枫
> 
> 博客主页：[流川枫的博客][Link 1]
> 
> 专栏：[和我一起学java][java]
> 
> 语录：Stay hungry stay foolish
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击注册和我一起刷题][Link 2]

![27a3f7a7b622423eba338fe1f5e4bfbe.png][]

> 题目描述
> 
> 判断两树是否相同
> 
> 给你两棵二叉树的根节点 `p` 和 `q` ，编写一个函数来检验这两棵树是否相同。
> 
> 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

![fdf2549b81d440fbae79c42843865683.png][]

![dd6013b0b58c41c3a9ec30eda7fbd6f7.png][]

> 分析：
> 
> 两个二叉树都为空，则两个二叉树相同。两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
> 
> 如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同
> 
> 这是一个递归的过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同

代码

/**
     * 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 isSameTree(TreeNode p, TreeNode q) {
    if(p==null && q==null){
            return true;
        }
    
        if(p!=null && q!=null && p.val==q.val  ){
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }else {
            return false;
        }
        }
    }

时间复杂度：O(min(m,n))，其中m和n分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数

空间复杂度：O(min(m,n))，其中 m和n 分别是两个二叉树的节点数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数

> “ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！

![ced485cbb11e458d81a746890b32cf3f.gif][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343
[java]: https://blog.csdn.net/chenchenchencl/category_11932758.html
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_qdmdlcf_c
[27a3f7a7b622423eba338fe1f5e4bfbe.png]: https://img-blog.csdnimg.cn/27a3f7a7b622423eba338fe1f5e4bfbe.png
[fdf2549b81d440fbae79c42843865683.png]: https://img-blog.csdnimg.cn/fdf2549b81d440fbae79c42843865683.png
[dd6013b0b58c41c3a9ec30eda7fbd6f7.png]: https://img-blog.csdnimg.cn/dd6013b0b58c41c3a9ec30eda7fbd6f7.png