给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
100. 相同的树
给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
输入:p = [1,2,3], q = [1,2,3]
输出:true
示例 2:
输入:p = [1,2], q = [1,null,2]
输出:false
示例 3:
输入:p = [1,2,1], q = [1,1,2]
输出:false
提示:
两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/same-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
标签:深度优先遍历
终止条件与返回值:
当两棵树的当前节点都为 null 时返回 true
当其中一个为 null 另一个不为 null 时返回 false
当两个都不为空但是值不相等时,返回 false
执行过程:当满足终止条件时进行返回,不满足时分别判断左子树和右子树是否相同,其中要注意代码中的短路效应
时间复杂度:O(n),n 为树的节点个数
作者:guanpengchn
链接:https://leetcode-cn.com/problems/same-tree/solution/hua-jie-suan-fa-100-xiang-tong-de-shu-by-guanpengc/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
代码
1 | /** |
__END__