一、题目
给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
二、示例
输入:p = [1,2,3], q = [1,2,3]
输出:true
输入:p = [1,2], q = [1,null,2]
输出:false
输入:p = [1,2,1], q = [1,1,2]
输出:false
三、思路
本题采用递归算法,存在三种情况,当两者都不存在值的时候直接返回true,当两者其中一个有值另一个没有的时候直接返回false。第三种情况就是都存在值,此时就想两者的值进行比较,然后再进行递归比较左节点和右节点。
四、代码
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function(p, q) {
if(!p && !q) {
return true
}else if(p && !q || !p && q) return false
else {
return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}
};
五、总结
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_47450807/article/details/123363409
内容来源于网络,如有侵权,请联系作者删除!