资讯详情

题目:
难度: 简单
知识点: 二叉树的 深度遍历DFS 和 广度遍历BFS

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
输入：p = [1,2,3], q = [1,2,3]
输出：true
输入：p = [1,2], q = [1,null,2]
输出：false

解法1:

• p 和 q 都为 null 的时候 相同
• p 和 q 只有一个为null 一定不相同
• 用递归比较两棵树的左子树和右子树,
• 有左子树并且值相同则左子树相同,
• 有右子树并且值相同则右子树相同

/*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.left = (left===undefined ? null : left)*         this.right = (right===undefined ? null : right)*     }* }*/function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {if(p == null && q == null) return true // p 和 q 都为 null 的时候 相同else if(p == null || q == null) return false // p 和 q 只有一个为null 一定不相同else if(p.val !== q.val) return falseelse return isSameTree(p.left,q.left) &&   isSameTree(p.right,q.right) 
};

解法2:

• p 和 q 都为 null 的时候 相同
• p 和 q 只有一个为null 一定不相同
• 使用 BFS 的方法来判断是否相同是相同树
• 当元素出队列时,判断值是否相同,不相同则直接return fasle
• 元素的左孩子入队列的时候,p和q一个为null 另一个不为null return fasle
• 元素的右孩子入队列的时候,p和q一个为null 另一个不为null return fasle
• 元素的左孩子右孩子不为null则入队列
• 最后 两个队列,有一个队列不为空的时候直接return fasle

/*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.left = (left===undefined ? null : left)*         this.right = (right===undefined ? null : right)*     }* }*/function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {if(p == null && q == null) return trueelse if(p == null || q == null) return falselet pQueue = [],qQueue = []pQueue.push(p)qQueue.push(q)while(pQueue.length){let pNode = pQueue.shift()let qNode = qQueue.shift()if(pNode?.val != qNode?.val ) return false// 一个为null,另一个不为null 就不相同// 相当于java种的这种写法// if (left1 == null ^ left2 == null) {//     return false;// }// // A ^ B 的结果：// - 如果 A 和 B 相同（都为true或都为false），结果为 false// - 如果 A 和 B 不同（一个true一个false），结果为 trueif((pNode.left == null) != (qNode.left == null)) return falseif((pNode.right == null) != (qNode.right == null)) return falseif(pNode.left) pQueue.push(pNode.left) if(pNode.right) pQueue.push(pNode.right)if(qNode.left) qQueue.push(qNode.left)if(qNode.right) qQueue.push(qNode.right)}return pQueue.length == 0 && qQueue.length == 0};