柳市建设网站做专业课视频课的网站

柳市建设网站,做专业课视频课的网站,成都网站建设怎么样,网站建设答辩每天学习一点算法 2025/12/18 题目#xff1a;对称二叉树 给你一个二叉树的根节点 root #xff0c; 检查它是否轴对称。 老规矩先来递归#xff0c; 检查二叉树是否轴对称#xff0c;我们是不是得比较根节点下面得两个子树是否是轴对称#xff0c;那么我们只需要递归比较…每天学习一点算法 2025/12/18题目对称二叉树给你一个二叉树的根节点root 检查它是否轴对称。老规矩先来递归 检查二叉树是否轴对称我们是不是得比较根节点下面得两个子树是否是轴对称那么我们只需要递归比较两个子树的值即可那要怎么传参呢首先肯定是要将根节点的两个子节点作为初始传参传进去的那么我们需要一个辅助函数然后每次递归对称传递子结点比较。functionisSymmetric(root:TreeNode|null):boolean{if(!root)returntrue;// 空树默认为true// 定义辅助函数 递归比较两个子树functionvalidate(left:TreeNode|null,right:TreeNode|null):boolean{// 两个子节点同时为空才有轴对称的可能if(!left!right)returntrue;if(!left||!right)returnfalse;// 比较左右子节点的值并传递对称的子节点递归returnleft.valright.valvalidate(left.left,right.right)validate(left.right,right.left);}// 调用辅助函数returnvalidate(root.left,root.right);};还有我们是不是可以用层序遍历的方法取得每一层的节点然后我们校验他们是否是对称就行了。核心思想其实跟递归是一样的找到对称节点作比较。如果我们拓展下一层按照左左↔右右、左右↔右左的顺序入队列那么每两个节点都是对称位置上的节点了比如说我们有一个四层的结构对称的树像下面这个样。1 / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15我们初始两个子节点入队列[2, 3]然后2, 3出队列子节点按照左左↔右右、左右↔右左的顺序入队列[4, 7, 5, 6]然后4, 7出队列子节点按照左左↔右右、左右↔右左的顺序入队列[5, 6, 8, 15, 9, 14]然后5, 6出队列子节点按照左左↔右右、左右↔右左的顺序入队列[8, 15, 9, 14, 10, 13, 11, 12]然后剩下的子节点两两出队列。可以看到整个循环的过程子节点的遍历是从上到下每层从两端向中间收拢的我们按照这种方式遍历比较两两出队列的节点值就可判断出树是否对称。functionisSymmetric(root:TreeNode|null):boolean{// 空树默认为对称if(!root)returntrue;// 初始化队列用于层序遍历对称位置的节点constqueue:ArrayTreeNode|null[];// 根节点的左右子节点都为空是对称树if(!root.left!root.right)returntrue;// 根节点的左右子节点只有一个为空必然不对称if(!root.left||!root.right)returnfalse;// 将根节点的左右子节点对称的起始节点入队queue.push(root.left);queue.push(root.right);// 层序遍历队列中的对称节点对while(queue.length){// 每次取出队列前两个节点一对对称节点constleftqueue.shift()!;constrightqueue.shift()!;// 两个节点都为空说明当前对称位置无节点继续检查下一对if(!left!right)continue;// 不对称的情况// 1. 其中一个节点为空另一个非空// 2. 两个节点值不相等if((!left||!right)||(left.val!right.val))returnfalse;// 按对称规则将下一层节点入队// 左节点的左子节点对应右节点的右子节点queue.push(left.left);queue.push(right.right);// 左节点的右子节点对应右节点的左子节点queue.push(left.right);queue.push(right.left);}// 所有对称节点对都验证通过说明是对称二叉树returntrue;}题目来源力扣LeetCode