电子商务网站建设课设网站模板,手机网站酷站,手机网站制作行业排行,wordpress旅游类网站相同的树
https://leetcode.cn/problems/same-tree/
描述 给你两棵二叉树的根节点 p 和 q #xff0c;编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同#xff0c;并且节点具有相同的值#xff0c;则认为它们是相同的。
示例 1 1 1/ \ / …相同的树
https://leetcode.cn/problems/same-tree/
描述 给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。
示例 1 1 1/ \ / \
2 3 2 3 输入p [1,2,3], q [1,2,3]
输出true示例 2 1 1/ \
2 2输入p [1,2], q [1,null,2]
输出false示例 3 1 1/ \ / \
2 1 1 2输入p [1,2,1], q [1,1,2]
输出false提示
两棵树上的节点数目都在范围 [0, 100] 内- 1 0 4 10^4 104 Node.val 1 0 4 10^4 104
算法实现
1 深度优先递归版本
/*** 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 (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? null : right)* }* }*/function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {// 都为空时if(!p !q) return true;// 不相同时if (p?.val ! q?.val) return false;// 递归判断return isSameTree(p?.left, q?.left) isSameTree(p?.right, q?.right);
};解题思路 两棵树相同根节点值相同左子树相同右子树相同如此一来我们把若干大问题分解成若干个相似小问题符合分、解、合特性选择分而治之 解题步骤 分获取两个树的左子树和右子树解递归地判断两个树的左子树是否相同右子树是否相同合将上述结果合并若根节点值也相同树就相同 时间复杂度O(n) n是所有节点数 空间复杂度O(n) 递归底部形成堆栈n是树的节点数最坏情况下树的节点数是树的高度
2 广度优先迭代版本
/*** 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 (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? null : right)* }* }*/function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {// 都为空时if(!p !q) return true;// 不相同时if (p?.val ! q?.val) return false;// 声明两个队列const queue1 [p];const queue2 [q];// 迭代对比while (queue1.length queue2.length) {// 拿到队首const pTop queue1.shift();const qTop queue2.shift();// 对比判断, 符合则提前终止if (pTop.val ! qTop.val) return false;// 拿到下一层const pLeft pTop?.left;const pRight pTop?.right;const qLeft qTop?.left;const qRight qTop?.right;// 进入判断, 符合则提前终止if ((pLeft !qLeft) || (!pLeft qLeft)) return false;if ((pRight !qRight) || (!pRight qRight)) return false;// 进入队列if (pLeft) queue1.push(pLeft);if (pRight) queue1.push(pRight);if (qLeft) queue2.push(qLeft);if (qRight) queue2.push(qRight);}// 最终结果对比return !queue1.length !queue2.length;
}这里换一种广度优先遍历来对比两棵树是否相同时间复杂度O(n)空间复杂度O(n)
