网站空间续费一年多少钱,安阳区号查询,手机品牌网站,网站开发重庆给「代码随想录」一个星标吧#xff01;❝有学习就要有总结❞本周小结本周赶上了十一国庆#xff0c;估计大家已经对本周末没什么概念了#xff0c;但是我们该做总结还是要做总结的。本周的主题其实是「简单但并不简单」#xff0c;本周所选的题目大多是看一下就会的题目❝有学习就要有总结❞本周小结本周赶上了十一国庆估计大家已经对本周末没什么概念了但是我们该做总结还是要做总结的。本周的主题其实是「简单但并不简单」本周所选的题目大多是看一下就会的题目但是大家看完本周的文章估计也发现了二叉树的简答题目其实里面都藏了很多细节。这些细节我都给大家展现了出来。周一本周刚开始我们讲解了判断二叉树是否对称的写法 二叉树我对称么。这道题目的本质是要比较两个树(这两个树是根节点的左右子树)遍历两棵树而且要比较内侧和外侧节点所以准确的来说是一个树的遍历顺序是左右中一个树的遍历顺序是右左中。而本题的迭代法中我们使用了队列需要注意的是这不是层序遍历而且仅仅通过一个容器来成对的存放我们要比较的元素认识到这一点之后就发现用队列用栈甚至用数组都是可以的。那么做完本题之后再看如下两个题目。100.相同的树572.另一个树的子树「二叉树我对称么中的递归法和迭代法只需要稍作修改其中一个树的遍历顺序便可刷了100.相同的树。」100.相同的树的递归代码如下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); }};100.相同的树精简之后代码如下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; else return compare(left-left, right-left) compare(left-right, right-right); } bool isSameTree(TreeNode* p, TreeNode* q) { return compare(p, q); }};100.相同的树迭代法代码如下lass Solution {public: bool isSameTree(TreeNode* p, TreeNode* q) { if (p NULL q NULL) return true; if (p NULL || q NULL) return false; queue que; que.push(p); que.push(q); while (!que.empty()) { TreeNode* leftNode que.front(); que.pop(); TreeNode* rightNode que.front(); que.pop();if (!leftNode !rightNode) { continue; }if ((!leftNode || !rightNode || (leftNode-val ! rightNode-val))) {return false; } // 相对于求对称二叉树这里两个树都要保持一样的遍历顺序 que.push(leftNode-left); que.push(rightNode-left); que.push(leftNode-right); que.push(rightNode-right); }return true; }};而572.另一个树的子树则和 100.相同的树几乎一样的了大家可以直接AC了。周二在二叉树看看这些树的最大深度中我们讲解了如何求二叉树的最大深度。本题可以使用前序也可以使用后序遍历(左右中)使用前序求的就是深度使用后序呢求的是高度。「而根节点的高度就是二叉树的最大深度」所以本题中我们通过后序求的根节点高度来求的二叉树最大深度所以二叉树看看这些树的最大深度中使用的是后序遍历。本题当然也可以使用前序代码如下(「充分表现出求深度回溯的过程」)class Solution {public: int result; void getDepth(TreeNode* node, int depth) { result depth result ? depth : result; // 中 if (node-left NULL node-right NULL) return ; if (node-left) { // 左 depth; // 深度1 getDepth(node-left, depth); depth--; // 回溯深度-1 } if (node-right) { // 右 depth; // 深度1 getDepth(node-right, depth); depth--; // 回溯深度-1 } return ; } int maxDepth(TreeNode* root) { result 0; if (root 0) return result; getDepth(root, 1); return result; }};「可以看出使用了前序(中左右)的遍历顺序这才是真正求深度的逻辑」注意以上代码是为了把细节体现出来简化一下代码如下class Solution {public: int result; void getDepth(TreeNode* node, int depth) { result depth result ? depth : result; // 中 if (node-left NULL node-right NULL) return ; if (node-left) { // 左 getDepth(node-left, depth 1); } if (node-right) { // 右 getDepth(node-right, depth 1); } return ; } int maxDepth(TreeNode* root) { result 0; if (root 0) return result; getDepth(root, 1); return result; }};周三在二叉树看看这些树的最小深度中我们讲解如何求二叉树的最小深度 这道题目要是稍不留心很容易犯错。「注意这里最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。」什么是叶子节点左右孩子都为空的节点才是叶子节点「求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。」注意到这一点之后 递归法和迭代法 都可以参照二叉树看看这些树的最大深度写出来。周四我们在二叉树我有多少个节点中讲解了如何求二叉树的节点数量。这一天是十一长假的第一天又是双节所以简单一些只要把之前两篇二叉树看看这些树的最大深度 二叉树看看这些树的最小深度都认真看了的话这道题目可以分分钟刷掉了。估计此时大家对这一类求二叉树节点数量以及求深度应该非常熟练了。周五在二叉树我平衡么中讲解了如何判断二叉树是否是平衡二叉树今天讲解一道判断平衡二叉树的题目其实 方法上我们之前讲解深度的时候都讲过了但是这次我们通过这道题目彻底搞清楚二叉树高度与深度的问题以及对应的遍历方式。二叉树节点的深度指从根节点到该节点的最长简单路径边的条数。二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数。「但leetcode中强调的深度和高度很明显是按照节点来计算的」。关于根节点的深度究竟是1 还是 0不同的地方有不一样的标准leetcode的题目中都是以节点为一度即根节点深度是1。但维基百科上定义用边为一度即根节点的深度是0我们暂时以leetcode为准(毕竟要在这上面刷题)。当然此题用迭代法其实效率很低因为没有很好的模拟回溯的过程所以迭代法有很多重复的计算。虽然理论上所有的递归都可以用迭代来实现但是有的场景难度可能比较大。「例如都知道回溯法其实就是递归但是很少人用迭代的方式去实现回溯算法」讲了这么多二叉树题目的迭代法有的同学会疑惑迭代法中究竟什么时候用队列什么时候用栈「如果是模拟前中后序遍历就用栈如果是适合层序遍历就用队列当然还是其他情况那么就是 先用队列试试行不行不行就用栈。」周六在二叉树找我的所有路径中正式涉及到了回溯很多同学过了这道题目可能都不知道自己使用了回溯其实回溯和递归都是相伴相生的。最后我依然给出了迭代法的版本。我在题解中第一个版本的代码会把回溯的过程充分体现出来如果大家直接看简洁的代码版本很可能就会忽略的回溯的存在。我在文中也强调了这一点。有的同学还不理解 文中精简之后的递归代码回溯究竟隐藏在哪里了。文中我明确的说了「回溯就隐藏在traversal(cur-left, path -, result);中的 path -。每次函数调用完path依然是没有加上- 的这就是回溯了。」如果还不理解的话可以把traversal(cur-left, path -, result);改成string tmp path -;traversal(cur-left, tmp, result);看看还行不行了答案是这么写就不行了因为没有回溯了。总结二叉树的题目我都是使用了递归三部曲一步一步的把整个过程分析出来而不是上来就给出简洁的代码。一些同学可能上来就能写出代码大体上也知道是为啥可以自圆其说但往细节一扣就不知道了。所以刚接触二叉树的同学建议按照文章分析的步骤一步一步来不要上来就照着精简的代码写(那样写完了也很容易忘的知其然不知其所以然)。「简短的代码看不出遍历的顺序也看不出分析的逻辑还会把必要的回溯的逻辑隐藏了所以尽量按照原理分析一步一步来写出来之后再去优化代码。」下周依然是二叉树大家加个油在留言区留下你的思路吧-------end-------我将算法学习相关的资料已经整理到了Github https://github.com/youngyangyang04/leetcode-master里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图看一看一定会有所收获如果给你有帮助给一个star支持一下吧另外因为公众号改版时间线被打乱一些精彩文章大家可能错过了。如果感觉这里的文章对你有帮助赶紧给「代码随想录」加一个星标吧方便第一时间阅读文章。往期精彩回顾二叉树找我的所有路径二叉树我平衡么二叉树我有多少个节点二叉树看看这些树的最小深度二叉树看看这些树的最大深度二叉树我对称么本周小结(二叉树)二叉树你真的会翻转二叉树么二叉树层序遍历登场二叉树前中后序迭代方式的写法就不能统一一下么二叉树听说递归能做的栈也能做二叉树一入递归深似海从此offer是路人关于二叉树你该了解这些「代码随想录」期待你的关注每天8:35准时推送一道经典算法题目推送的每道题目都不是孤立的而是由浅入深环环相扣帮你梳理算法知识脉络轻松学算法刷题可以加我微信右边为个人微信添加时备注「简单自我介绍」「组队刷题」我就知道你[在看]
