建设银行官方网站入口,网站建设预期达到的效果,不用付费全部免费的追剧软件,枸杞网站建设方案#试题28#xff1a;对称的二叉树
题目#xff1a;
请设计一个函数判断一棵二叉树是否 轴对称 。
示例 1#xff1a; 输入#xff1a;root [6,7,7,8,9,9,8]
输出#xff1a;true
解释#xff1a;从图中可看出树是轴对称的。示例 2#xff1a; 输入#xff1a;root …#试题28对称的二叉树
题目
请设计一个函数判断一棵二叉树是否 轴对称 。
示例 1 输入root [6,7,7,8,9,9,8]
输出true
解释从图中可看出树是轴对称的。示例 2 输入root [1,2,2,null,3,null,3]
输出false
解释从图中可看出最后一层的节点不对称。思路
1.中序遍历是左中右所以初步想法是使用中序遍历把二叉树遍历一遍添加到容器中这时候要把空着的节点以null的形式添加进容器针对这种[1,2,2,2,null,2]树结构然后把容器分为两段比较他们的值从而得出是否是对称二叉树
2.书中的想法是使用迭代的思路将比较左右两个节点判断他们的情况一共有四种情况都为空true一个为空一个不为空false值不一样false值一样则继续判断左节点的左子节点与右节点的右子节点情况左节点的右子节点与右节点的左子节点情况
代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool check(TreeNode* root_left,TreeNode* root_right){if(root_leftnullptrroot_rightnullptr)return true;if(root_leftnullptr || root_rightnullptr)return false;if(root_left-val!root_right-val)return false;return check(root_left-left,root_right-right) check(root_left-right,root_right-left);}bool checkSymmetricTree(TreeNode* root) {return check(root,root);}
};leetcode101题
考点
考察对二叉树的理解实质上是利用树的遍历算法解决问题。考察思维能力树的对称是一个抽象的概念需要微秒在短时间内清楚判断对称的步骤并转化为代码