温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

LeetCode中如何解决相同的树问题

发布时间:2022-01-17 11:51:31 阅读:110 作者:小新 栏目:大数据
开发者测试专用服务器限时活动,0元免费领,库存有限,领完即止! 点击查看>>

这篇文章将为大家详细讲解有关LeetCode中如何解决相同的树问题,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。

 

题目链接

https://leetcode-cn.com/problems/same-tree/

 

题目描述

给定两个二叉树,编写一个函数来检验它们是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

输入:       1         1          / \       / \         2   3     2   3        [1,2,3],   [1,2,3]输出: true
 

示例 2:

输入:      1          1          /           \         2             2        [1,2],     [1,null,2]输出: false
 

示例 3:

输入:       1         1          / \       / \         2   1     1   2        [1,2,1],   [1,1,2]输出: false
   

解题方案

 

思路

  • 标签:深度优先遍历

  • 终止条件与返回值:

    • 当两棵树的当前节点都为null时返回true

    • 当其中一个为null另一个不为null时返回false

    • 当两个都不为空但是值不相等时,返回false

  • 执行过程:当满足终止条件时进行返回,不满足时分别判断左子树和右子树是否相同,其中要注意代码中的短路效应

  • 时间复杂度:O(n),n为树的节点个数

 

代码

  • Java版本

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public boolean isSameTree(TreeNode p, TreeNode q) {        if(p == null && q == null)            return true;        if(p == null || q == null)            return false;        if(p.val != q.val)            return false;        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);    }}
 
  • JavaScript版本

/** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } *//** * @param {TreeNode} p * @param {TreeNode} q * @return {boolean} */var isSameTree = function(p, q) {    if(p == null && q == null)        return true;    if(p == null || q == null)        return false;    if(p.val != q.val)        return false;    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);};
   

画解

LeetCode中如何解决相同的树问题

LeetCode中如何解决相同的树问题

LeetCode中如何解决相同的树问题

关于“LeetCode中如何解决相同的树问题”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。

亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

原文链接:https://my.oschina.net/u/2446442/blog/4379954

AI

开发者交流群×