外贸网站模板免费下载,最新做做网站,jsp电子商务网站建设源码,广西桂林对称二叉树
https://leetcode.cn/problems/symmetric-tree/
描述
给你一个二叉树的根节点 root #xff0c; 检查它是否轴对称。
示例 1 1/ | \2 | 2/ \ | / \3 4 | 4 3中间一条线是对称轴
输入#xff1a;root [1,2,2,3,4,4,3]
输出#xff1a;true示例 …对称二叉树
https://leetcode.cn/problems/symmetric-tree/
描述
给你一个二叉树的根节点 root 检查它是否轴对称。
示例 1 1/ | \2 | 2/ \ | / \3 4 | 4 3中间一条线是对称轴
输入root [1,2,2,3,4,4,3]
输出true示例 2 1/ \
2 2\ \3 3输入root [1,2,2,null,3,null,3]
输出false提示
树中节点数目在范围 [1, 1000] 内-100 Node.val 100
算法实现
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 isSymmetric(root: TreeNode | null): boolean {if(!root) return true;const isMirror (l: TreeNode | null, r: TreeNode | null) {if(!l !r) return true; // 空树是镜像的return l?.val r?.val isMirror(l?.left, r?.right) isMirror(r?.left, l?.right)};return isMirror(root.left, root.right);
}解题思路 转化为左右子树是否镜像分解为树1的左子树和树2的左子树是否镜像树1的右子树和树2的左子树是否镜像成立且根节点值相同则镜像符合分、解、合的特性考虑分而治之 解题步骤 分获取两个树的左子树和右子树解递归地判断树1的左子树和树2的右子树是否镜像树1的右子树和树2的左子树是否镜像合如果上述两个都成立且根节点值也相同两个树就是镜像 时间复杂度O(n) 叶子节点数量 空间复杂度: O(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 isSymmetric(root: TreeNode | null): boolean {if(!root || (!root.left !root.right)) return true;const queue: (TreeNode | null)[] [root.left, root.right];while(queue.length) {const left queue.shift();const right queue.shift();// 如果两个节点都为空就继续循环两者有一个为空就返回falseif (!left !right) continue;if (!left || !right) return false;if (left.val ! right.val) return false;// 将左节点的左孩子, 右节点的右孩子 存入队列queue.push(left.left);queue.push(right.right);// 将左节点的右孩子 和 右节点的左孩子 存入队列queue.push(left.right);queue.push(right.left);}return true;
}使用广度优先遍历来替代深度优先遍历实现对称校验时间复杂度是 O(n)空间复杂度是 O(n)
