海南建设官方信息网站,可以网站可以做免费的文案广告,免费企业网站怎么做,典当行网站模板#x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;练题 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录 二叉树的层序遍历翻转二叉树… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接练题 长路漫漫浩浩万事皆有期待 文章目录 二叉树的层序遍历翻转二叉树对称二叉树总结 二叉树的层序遍历
二叉树的层序遍历就是广度优先搜索的一种典型实例题解思路十分重要先说广搜的原理它的原理就是使用队列这个数据结构将每一层需要遍历的数据放入到队列中然后将他们的下一层放入队列后取出本层的数据循环往复直到队列为空说明遍历结束
102. 二叉树的层序遍历 - 力扣LeetCode
这道题是考察广搜的经典题目
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode*q;vectorvectorintresult;vectorintres;if(root)q.push(root);while(!q.empty()){int sizeq.size();while(size--){// 这里一定要使用固定大小size不要使用que.size()因为que.size是不断变化的TreeNode*nodeq.front();q.pop();res.push_back(node-val);if(node-left)q.push(node-left);if(node-right)q.push(node-right);}result.push_back(res);res.clear();}return result;}
};前面已经说了广搜要创建队列我们创建好队列了之后 将头节点加入队列然后创立一个size变量用来保存当前数层中元素的个数这一点很重要我们要知道当前数层中有几个数据才能知道要取出几个数据接着我们进入循环在循环中用size来判断多久跳出循环在循环中我们要做的事情就是将数据加入答案数组中以及将本层数据节点的全部左右孩子都加入进来实际上每次加入的是队列头部元素的左右孩子通过不断循环最后才都加入进来最后将本层数组加入最后的数组不要忘记将本层数组清空再进行下一次的循环。
递归法
class Solution {
public:void order(TreeNode* cur, vectorvectorint result, int depth){if (cur nullptr) return;if (result.size() depth) result.push_back(vectorint());result[depth].push_back(cur-val);order(cur-left, result, depth 1);order(cur-right, result, depth 1);}vectorvectorint levelOrder(TreeNode* root) {vectorvectorint result;int depth 0;order(root, result, depth);return result;}
};翻转二叉树
226. 翻转二叉树 - 力扣LeetCode
翻转二叉树实际上就是沿着对称轴反转注意不能直接交换节点的数值而是要交换指针。
这道题刚做的时候不太有思路不知道从何做起后来看了题解才明白。 思路为将二叉树的左右孩子节点依次反转即能完成题目要求
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(rootnullptr)return root;invertTree(root-left);invertTree(root-right);swap(root-left,root-right);return root;}
};前两步就是一直向下找直到找到最左侧的节点然后走第二步递归找到和最左侧相邻的右侧节点然后进行交换节点完成节点指针交换代码十分的简洁利于理解。这样的代码风格有点类似于二叉树中的后序遍历顺序实际上前序也是可以的它只不过是先将根节点的左右孩子节点反转再向下遍历反转后序是先反转最下面的节点区别仅此而已都可以完成题目要求。
但是值得一提的是中序并不只是将交换数据的代码插入到中间而已经过二叉树翻转模拟可知中序翻转时先翻转左子树后左右子树会交换这时我们在处理右子树实际上是处理刚才刚处理过的左子树实际上的右子树并没有经过处理所以要把第二三句代码改为root-left才能够完成对真正右子树的翻转。
对称二叉树
101. 对称二叉树 - 力扣LeetCode
对称二叉树的这道题和上一道题翻转二叉树的思路有着某些相似之处。起初我以为是要将该二叉树翻转之后判断和之前二叉树是否相等呢但是实际做的时候遇到了一些问题比如要做模板的二叉树也就是没改动之前的二叉树怎么存储呢实际上这种做法浪费了更多的空间。
更好的思路应该是判断二叉树的外侧对应各节点和内侧的对应各节点是否完全相等如果相等则说明是对称二叉树这样的思路并不需要额外开辟空间实践运用上我想应该和上一种思路差不多都要递归遍历求解。
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;return compare(root-left, root-right);}
};代码虽然没有那么简洁但是思路十分清晰先是把我们可能跳出递归的所有可能都列了出来即左节点为空右节点不为空左节点不为空但是右节点为空的情况还有左右节点不为空但是值不对应相等这三种判断完了之后那就剩下左右都为空或者都不为空且对应值相等很明显这两种都是合法的这里针对都不为空且对应值相等我们不做判断的原因是因为前面能跳出的情况我们都做了判断并且两节点不为空且值相等并不是判断正确的理由它仅仅是我们当前对应节点正确它应该是我们能够向下遍历的一个原因而当全部节点都对应完了还没跳出两个指向应该同时指向空代表了当前内侧或外侧遍历完毕对应相等所以我们这时候再进行判断true。
总结
今天我们完成了二叉树的层序遍历、翻转二叉树、对称二叉树三道题目相关的思想需要多复习回顾。接下来我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
