建设旅游网站财务分析,手机网站域名解析,帝国网站做地域标签,网站开发数据共享题目
101. 对称二叉树
简单
给你一个二叉树的根节点 root #xff0c; 检查它是否轴对称。 示例 1#xff1a; 输入#xff1a;root [1,2,2,3,4,4,3]
输出#xff1a;true示例 2#xff1a; 输入#xff1a;root [1,2,2,null,3,null,3]
输出#xff1a;false提示 检查它是否轴对称。 示例 1 输入root [1,2,2,3,4,4,3]
输出true示例 2 输入root [1,2,2,null,3,null,3]
输出false提示
树中节点数目在范围 [1, 1000] 内-100 Node.val 100 进阶你可以运用递归和迭代两种方法解决这个问题吗
思路和解题方法一递归 compare()函数是用来判断两个节点是否对称的其中left和right参数分别代表左右子节点。 首先我们需要判断left和right是否为空若其中一个节点为空而另一个不为空那么这两个节点不对称返回false。如果两个节点都为空则认为它们对称返回true。 如果两个节点的值不相等则说明它们不对称返回false。 如果两个节点的值相等则需要递归判断它们的左右子节点是否对称。具体来说需要比较左子树的左子节点和右子树的右子节点、左子树的右子节点和右子树的左子节点是否对称即outside compare(left-left, right-right)和inside compare(left-right, right-left)。 最后给出判断结果即只有当左子树的左子节点和右子树的右子节点、左子树的右子节点和右子树的左子节点都对称时才可以认为这两个节点对称返回isSame outside inside。 isSymmetric()函数是判断整个二叉树是否对称的。如果给定的根节点root为空则直接返回true。否则调用compare()函数比较根节点的左右子节点是否对称。 最后整个程序返回的是isSymmetric()函数的返回值。 复杂度 时间复杂度: O(n) 时间复杂度是O(n)其中n为二叉树的节点数因为我们需要遍历每个节点每个节点都需要进行一次比较。 空间复杂度 O(n) 空间复杂度也是O(n)因为在递归调用compare()函数时需要不断开辟新的栈空间来存储递归函数的参数和局部变量最坏的情况下需要递归到最深层此时栈空间的大小为O(n)。 c 代码 //复杂简单版
class Solution {
public:// 判断节点是否对称的函数bool compare(TreeNode* left, TreeNode* right) {// 首先排除空节点的情况if (left NULL right ! NULL) return false;else if (left ! NULL right NULL) return false;else if (left NULL right NULL) return true;// 排除了空节点再排除数值不相同的情况else if (left-val ! right-val) return false;// 此时就是左右节点都不为空且数值相同的情况// 此时才做递归做下一层的判断bool outside compare(left-left, right-right); // 左子树左、 右子树右bool inside compare(left-right, right-left); // 左子树右、 右子树左bool isSame outside inside; // 左子树中、 右子树中 逻辑处理return isSame;}// 判断整棵二叉树是否对称的函数bool isSymmetric(TreeNode* root) {if (root NULL) return true;// 如果根节点不为空调用compare()函数比较左子节点和右子节点是否对称return compare(root-left, root-right);}
};//精简版
class Solution {
public:// 检查两个节点是否对称的函数bool check(TreeNode *p, TreeNode *q) {// 如果两个节点都为空视为对称if (!p !q) return true;// 如果其中一个节点为空另一个节点非空视为不对称if (!p || !q) return false;// 检查当前节点的值是否相等并递归检查左子树和右子树是否对称return p-val q-val check(p-left, q-right) check(p-right, q-left);}// 判断整棵二叉树是否对称的函数bool isSymmetric(TreeNode* root) {// 调用check函数同时传入相同的根节点判断左子树和右子树是否对称return check(root, root);}
};思路和解题方法二迭代 首先检查根节点是否为空若为空直接返回true。 创建一个队列que并将根节点的左子树和右子树头结点依次加入队列。 进入while循环判断队列是否为空。如果队列不为空则继续执行循环体。 在循环体中从队列中取出两个节点leftNode为队列首部的节点rightNode为队列次首部的节点。 判断左节点和右节点是否都为空。如果是说明当前节点属于对称的部分继续循环。 如果左节点和右节点有一个为空或者它们的值不相等返回false表示不对称。 如果左节点和右节点都不为空且值相等将其左孩子、右孩子按顺序依次加入队列以备后续判断是否对称。 循环结束后返回true表示二叉树是对称的。 复杂度 时间复杂度: O(n) 时间复杂度为O(n)其中n是二叉树的节点数。 空间复杂度 O(n) 使用了一个队列来存储节点因此空间复杂度为O(n)。 c 代码
class Solution {
public:bool isSymmetric(TreeNode* root) { // 判断二叉树是否对称的函数传入根节点rootif (root NULL) return true; // 如果根节点为空返回truequeueTreeNode* que; // 创建一个队列que来存储需要判断的节点que.push(root-left); // 将左子树头结点加入队列que.push(root-right); // 将右子树头结点加入队列while (!que.empty()) { // 当队列不为空时进行循环TreeNode* leftNode que.front(); que.pop(); // 取出队列首部的节点leftNodeTreeNode* rightNode que.front(); que.pop(); // 取出队列次首部的节点rightNodeif (!leftNode !rightNode) { // 如果左节点为空、右节点为空说明是对称的继续循环continue;}// 左右一个节点不为空或者都不为空但数值不相同返回falseif ((!leftNode || !rightNode || (leftNode-val ! rightNode-val))) {return false; // 如果左右节点有一个为空或者值不相等直接返回false表示当前二叉树不对称}// 加入左节点左孩子、右节点右孩子、左节点右孩子、右节点左孩子que.push(leftNode-left); // 左节点的左孩子que.push(rightNode-right); // 右节点的右孩子que.push(leftNode-right); // 左节点的右孩子que.push(rightNode-left); // 右节点的左孩子}return true; // 当循环结束时说明整个二叉树都对称返回true}
};觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
