题目:
难度: 简单
知识点: 二叉树的 深度遍历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};