这篇文章将为大家详细讲解有关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中如何解决相同的树问题”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/2446442/blog/4379954