网站发展阶段怎么做,做公号模版网站,网站设计班培训,wordpress v4代码随想录算法训练营第二十天#xff1a;二叉树成长
110.平衡二叉树
力扣题目链接(opens new window)
给定一个二叉树#xff0c;判断它是否是高度平衡的二叉树。
本题中#xff0c;一棵高度平衡二叉树定义为#xff1a;一个二叉树每个节点 的左右两个子树的高度差的绝…代码随想录算法训练营第二十天二叉树成长
110.平衡二叉树
力扣题目链接(opens new window)
给定一个二叉树判断它是否是高度平衡的二叉树。
本题中一棵高度平衡二叉树定义为一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
返回 false 。
#算法公开课
《代码随想录》算法视频公开课 ****(opens new window)**** 后序遍历求高度高度判断是否平衡 | LeetCode110.平衡二叉树 ****(opens new window)**** 相信结合视频在看本篇题解更有助于大家对本题的理解。
#题外话
咋眼一看这道题目和104.二叉树的最大深度 **(opens new window)** 很像其实有很大区别。
这里强调一波概念
二叉树节点的深度指从根节点到该节点的最长简单路径边的条数。二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数。
但leetcode中强调的深度和高度很明显是按照节点来计算的如图
关于根节点的深度究竟是1 还是 0不同的地方有不一样的标准leetcode的题目中都是以节点为一度即根节点深度是1。但维基百科上定义用边为一度即根节点的深度是0我们暂时以leetcode为准毕竟要在这上面刷题。
因为求深度可以从上到下去查 所以需要前序遍历中左右而高度只能从下到上去查所以只能后序遍历左右中
有的同学一定疑惑为什么104.二叉树的最大深度 **(opens new window)** 中求的是二叉树的最大深度也用的是后序遍历。
那是因为代码的逻辑其实是求的根节点的高度而根节点的高度就是这棵树的最大深度所以才可以使用后序遍历。
在104.二叉树的最大深度 **(opens new window)** 中如果真正求取二叉树的最大深度代码应该写成如下前序遍历
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; // 深度1getDepth(node-left, depth);depth--; // 回溯深度-1}if (node-right) { // 右depth; // 深度1getDepth(node-right, depth);depth--; // 回溯深度-1}return ;}int maxDepth(TreeNode* root) {result 0;if (root NULL) return result;getDepth(root, 1);return result;}
};
这段代码是计算给定二叉树的最大深度。为了理解为什么在depth之后又进行了depth--需要先明白递归过程中栈调用栈的使用以及回溯Backtracking的概念。 ### 递归过程 在递归过程中每次调用getDepth时当前函数的局部变量比如本例中的depth都会保存在调用栈上。当递归调用返回时会弹出栈顶元素恢复到调用之前的状态保证每一层递归的上下文环境是独立的。 ### 为什么需要depth-- 这里的depth和随后的depth--是为了在递归调用过程中正确管理深度计数。 1. depth : 当你进入一个子节点时深度增加1表示当前从根到这个子节点的路径长度增加了1。 2. 继续递归调用: 递归调用子节点的getDepth此时传递的depth值是增加后的值反映了当前的正确深度。 3. depth-- : 当你完成了当前子节点的递归处理后即将回到其父节点此时需要将深度减1回溯。这是因为你即将离开当前节点返回到上一层深度自然要减少1以确保深度计数正确无误代表从根节点到当前处理节点的距离。 ### 回溯的作用 回溯depth--保证了每当递归返回上一层时深度depth都能准确表示当前的树层级。这样无论是往左子树深入还是从左子树回溯后向右子树深入depth都能准确地代表从根到当前节点的路径长度。 简而言之depth和随后的depth--是为了确保在递归过程中对树的每个节点进行遍历时深度变量depth都能正确地反映当前节点的层级这对于计算二叉树的最大深度是关键所在。
可以看出使用了前序中左右的遍历顺序这才是真正求深度的逻辑
简化代码如下
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;}
};在这个优化后的递归版本中你去掉了手动的depth--操作使用depth 1来直接传递给递归调用。这一变化有效地简化了代码同时保留了原始逻辑的精髓。 ### 为什么不需要depth--了 在这个版本的代码中每次递归调用 getDepth 时你不是直接修改 depth 变量而是传递一个增加了的值 depth 1。这样做有几个好处 1. 不改变当前depth值 你不再需要在递归调用后将depth减一因为在递归调用时depth的值本身并没有改变。你传递的是depth 1的新值而当前作用域中的depth保持不变。 2. 简化代码 这种方式简化了逻辑使其更容易阅读和理解。没有必要增加然后再减同一个变量只要在需要增加深度时传递增加后的值即可。 3. 保持不变性 这种策略保持了函数参数depth的不变性即在整个getDepth函数调用过程中传入的深度值depth在函数体内不会被修改只会以新的值传递给递归调用。这样做有利于避免副作用使得每次递归调用都基于明确的、明智的状态。 ### 技术解释 当你调用getDepth(node-left, depth 1)实际上你是在以node-left为根的子树上递归调用getDepth同时将其深度视作depth 1。同理调用getDepth(node-right, depth 1)时也是进行相同的操作。由于每次递归都是创建新的调用栈帧而且传给递归函数的是值参数即深拷贝的值而非引用或指针这意味着每层递归使用的depth值都是独立的不存在需要恢复即递减到原先状态的必要。 总的来说这种方式通过向子递归传递更新后的值来避免了depth的手动增减操作使代码更加清晰和高效。
本题思路
#递归
此时大家应该明白了既然要求比较高度必然是要后序遍历。
递归三步曲分析
明确递归函数的参数和返回值
参数当前传入节点。 返回值以当前传入节点为根节点的树的高度。
那么如何标记左右子树是否差值大于1呢
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了还返回高度的话就没有意义了。
所以如果已经不是二叉平衡树了可以返回-1 来标记已经不符合平衡树的规则了。
代码如下
// -1 表示已经不是平衡二叉树了否则返回值是以该节点为根节点树的高度
int getHeight(TreeNode* node)明确终止条件
递归的过程中依然是遇到空节点了为终止返回0表示当前节点为根节点的树高度为0
代码如下
if (node NULL) {return 0;
}明确单层递归的逻辑
如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢当然是其左子树高度和其右子树高度的差值。
分别求出其左右子树的高度然后如果差值小于等于1则返回当前二叉树的高度否则返回-1表示已经不是二叉平衡树了。
代码如下
int leftHeight getHeight(node-left); // 左
if (leftHeight -1) return -1;
int rightHeight getHeight(node-right); // 右
if (rightHeight -1) return -1;int result;
if (abs(leftHeight - rightHeight) 1) { // 中result -1;
} else {result 1 max(leftHeight, rightHeight); // 以当前节点为根节点的树的最大高度
}return result;代码精简之后如下
int leftHeight getHeight(node-left);
if (leftHeight -1) return -1;
int rightHeight getHeight(node-right);
if (rightHeight -1) return -1;
return abs(leftHeight - rightHeight) 1 ? -1 : 1 max(leftHeight, rightHeight);此时递归的函数就已经写出来了这个递归的函数传入节点指针返回以该节点为根节点的二叉树的高度如果不是二叉平衡树则返回-1。
getHeight整体代码如下
int getHeight(TreeNode* node) {if (node NULL) {return 0;}int leftHeight getHeight(node-left);if (leftHeight -1) return -1;int rightHeight getHeight(node-right);if (rightHeight -1) return -1;return abs(leftHeight - rightHeight) 1 ? -1 : 1 max(leftHeight, rightHeight);
}最后本题整体递归代码如下
class Solution {
public:// 返回以该节点为根节点的二叉树的高度如果不是平衡二叉树了则返回-1int getHeight(TreeNode* node) {if (node NULL) {return 0;}int leftHeight getHeight(node-left);if (leftHeight -1) return -1;int rightHeight getHeight(node-right);if (rightHeight -1) return -1;return abs(leftHeight - rightHeight) 1 ? -1 : 1 max(leftHeight, rightHeight);}bool isBalanced(TreeNode* root) {return getHeight(root) -1 ? false : true;}
};迭代
在104.二叉树的最大深度 **(opens new window)** 中我们可以使用层序遍历来求深度但是就不能直接用层序遍历来求高度了这就体现出求高度和求深度的不同。
本题的迭代方式可以先定义一个函数专门用来求高度。
这个函数通过栈模拟的后序遍历找每一个节点的高度其实是通过求传入节点为根节点的最大深度来求的高度
代码如下
// cur节点的最大深度就是cur的高度
int getDepth(TreeNode* cur) {stackTreeNode* st;if (cur ! NULL) st.push(cur);int depth 0; // 记录深度int result 0;while (!st.empty()) {TreeNode* node st.top();if (node ! NULL) {st.pop();st.push(node); // 中st.push(NULL);depth;if (node-right) st.push(node-right); // 右if (node-left) st.push(node-left); // 左} else {st.pop();node st.top();st.pop();depth--;}result result depth ? result : depth;}return result;
}然后再用栈来模拟后序遍历遍历每一个节点的时候再去判断左右孩子的高度是否符合代码如下
bool isBalanced(TreeNode* root) {stackTreeNode* st;if (root NULL) return true;st.push(root);while (!st.empty()) {TreeNode* node st.top(); // 中st.pop();if (abs(getDepth(node-left) - getDepth(node-right)) 1) { // 判断左右孩子高度是否符合return false;}if (node-right) st.push(node-right); // 右空节点不入栈if (node-left) st.push(node-left); // 左空节点不入栈}return true;
}整体代码如下
class Solution {
private:int getDepth(TreeNode* cur) {stackTreeNode* st;if (cur ! NULL) st.push(cur);int depth 0; // 记录深度int result 0;while (!st.empty()) {TreeNode* node st.top();if (node ! NULL) {st.pop();st.push(node); // 中st.push(NULL);depth;if (node-right) st.push(node-right); // 右if (node-left) st.push(node-left); // 左} else {st.pop();node st.top();st.pop();depth--;}result result depth ? result : depth;}return result;}public:bool isBalanced(TreeNode* root) {stackTreeNode* st;if (root NULL) return true;st.push(root);while (!st.empty()) {TreeNode* node st.top(); // 中st.pop();if (abs(getDepth(node-left) - getDepth(node-right)) 1) {return false;}if (node-right) st.push(node-right); // 右空节点不入栈if (node-left) st.push(node-left); // 左空节点不入栈}return true;}
};当然此题用迭代法其实效率很低因为没有很好的模拟回溯的过程所以迭代法有很多重复的计算。
虽然理论上所有的递归都可以用迭代来实现但是有的场景难度可能比较大。
例如都知道回溯法其实就是递归但是很少人用迭代的方式去实现回溯算法
因为对于回溯算法已经是非常复杂的递归了如果再用迭代的话就是自己给自己找麻烦效率也并不一定高。
#总结
通过本题可以了解求二叉树深度 和 二叉树高度的差异求深度适合用前序遍历而求高度适合用后序遍历。
本题迭代法其实有点复杂大家可以有一个思路也不一定说非要写出来。
但是递归方式是一定要掌握的
257. 二叉树的所有路径
力扣题目链接(opens new window)
给定一个二叉树返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
#算法公开课
《代码随想录》算法视频公开课 ****(opens new window)**** 递归中带着回溯你感受到了没| LeetCode257. 二叉树的所有路径 ****(opens new window)**** 相信结合视频在看本篇题解更有助于大家对本题的理解。
#思路
这道题目要求从根节点到叶子的路径所以需要前序遍历这样才方便让父节点指向孩子节点找到对应的路径。
在这道题目中将第一次涉及到回溯因为我们要把路径记录下来需要回溯来回退一个路径再进入另一个路径。
前序遍历以及回溯的过程如图
递归
递归函数参数以及返回值
要传入根节点记录每一条路径的path和存放结果集的result这里递归不需要返回值代码如下
void traversal(TreeNode* cur, vectorint path, vectorstring result)确定递归终止条件
在写递归的时候都习惯了这么写
if (cur NULL) {终止处理逻辑
}但是本题的终止条件这样写会很麻烦因为本题要找到叶子节点就开始结束的处理逻辑了把路径放进result里。
那么什么时候算是找到了叶子节点 是当 cur不为空其左右孩子都为空的时候就找到叶子节点。
所以本题的终止条件是
if (cur-left NULL cur-right NULL) {终止处理逻辑
}为什么没有判断cur是否为空呢因为下面的逻辑可以控制空节点不入循环。
再来看一下终止处理的逻辑。
这里使用vector 结构path来记录路径所以要把vector 结构的path转为string格式再把这个string 放进 result里。
那么为什么使用了vector 结构来记录路径呢 因为在下面处理单层递归逻辑的时候要做回溯使用vector方便来做回溯。
可能有的同学问了我看有些人的代码也没有回溯啊。
其实是有回溯的只不过隐藏在函数调用时的参数赋值里下文我还会提到。
这里我们先使用vector结构的path容器来记录路径那么终止处理逻辑如下
if (cur-left NULL cur-right NULL) { // 遇到叶子节点string sPath;for (int i 0; i path.size() - 1; i) { // 将path里记录的路径转为string格式sPath to_string(path[i]);sPath -;}sPath to_string(path[path.size() - 1]); // 记录最后一个节点叶子节点result.push_back(sPath); // 收集一个路径return;
}确定单层递归逻辑
因为是前序遍历需要先处理中间节点中间节点就是我们要记录路径上的节点先放进path中。
path.push_back(cur-val);
然后是递归和回溯的过程上面说过没有判断cur是否为空那么在这里递归的时候如果为空就不进行下一层递归了。
所以递归前要加上判断语句下面要递归的节点是否为空如下
if (cur-left) {traversal(cur-left, path, result);
}
if (cur-right) {traversal(cur-right, path, result);
}此时还没完递归完要做回溯啊因为path 不能一直加入节点它还要删节点然后才能加入新的节点。
那么回溯要怎么回溯呢一些同学会这么写如下
if (cur-left) {traversal(cur-left, path, result);
}
if (cur-right) {traversal(cur-right, path, result);
}
path.pop_back();这个回溯就有很大的问题我们知道回溯和递归是一一对应的有一个递归就要有一个回溯这么写的话相当于把递归和回溯拆开了 一个在花括号里一个在花括号外。
所以回溯要和递归永远在一起世界上最遥远的距离是你在花括号里而我在花括号外
那么代码应该这么写
if (cur-left) {traversal(cur-left, path, result);path.pop_back(); // 回溯
}
if (cur-right) {traversal(cur-right, path, result);path.pop_back(); // 回溯
}那么本题整体代码如下
// 版本一
class Solution {
private:void traversal(TreeNode* cur, vectorint path, vectorstring result) {path.push_back(cur-val); // 中中为什么写在这里因为最后一个节点也要加入到path中 // 这才到了叶子节点if (cur-left NULL cur-right NULL) {string sPath;for (int i 0; i path.size() - 1; i) {sPath to_string(path[i]);sPath -;}sPath to_string(path[path.size() - 1]);result.push_back(sPath);return;}if (cur-left) { // 左 traversal(cur-left, path, result);path.pop_back(); // 回溯}if (cur-right) { // 右traversal(cur-right, path, result);path.pop_back(); // 回溯}}public:vectorstring binaryTreePaths(TreeNode* root) {vectorstring result;vectorint path;if (root NULL) return result;traversal(root, path, result);return result;}
};如上的C代码充分体现了回溯。
那么如上代码可以精简成如下代码
class Solution {
private:void traversal(TreeNode* cur, string path, vectorstring result) {path to_string(cur-val); // 中if (cur-left NULL cur-right NULL) {result.push_back(path);return;}if (cur-left) traversal(cur-left, path -, result); // 左if (cur-right) traversal(cur-right, path -, result); // 右}public:vectorstring binaryTreePaths(TreeNode* root) {vectorstring result;string path;if (root NULL) return result;traversal(root, path, result);return result;}
};如上代码精简了不少也隐藏了不少东西。
注意在函数定义的时候void traversal(TreeNode* cur, string path, vectorstring result) 定义的是string path每次都是复制赋值不用使用引用否则就无法做到回溯的效果。这里涉及到C语法知识
那么在如上代码中貌似没有看到回溯的逻辑其实不然回溯就隐藏在traversal(cur-left, path -, result); 中的 path - 。 每次函数调用完path依然是没有加上- 的这就是回溯了。
为了把这份精简代码的回溯过程展现出来大家可以试一试把
if (cur-left) traversal(cur-left, path -, result); // 左 回溯就隐藏在这里改成如下代码
path -;
traversal(cur-left, path, result); // 左即
if (cur-left) {path -;traversal(cur-left, path, result); // 左
}
if (cur-right) {path -;traversal(cur-right, path, result); // 右
}此时就没有回溯了这个代码就是通过不了的了。
如果想把回溯加上就要 在上面代码的基础上加上回溯就可以AC了。
if (cur-left) {path -;traversal(cur-left, path, result); // 左path.pop_back(); // 回溯 path.pop_back(); // 回溯 -
}
if (cur-right) {path -;traversal(cur-right, path, result); // 右path.pop_back(); // 回溯 path.pop_back(); // 回溯 -
}整体代码如下
//版本二
class Solution {
private:void traversal(TreeNode* cur, string path, vectorstring result) {path to_string(cur-val); // 中中为什么写在这里因为最后一个节点也要加入到path中if (cur-left NULL cur-right NULL) {result.push_back(path);return;}if (cur-left) {path -;traversal(cur-left, path, result); // 左path.pop_back(); // 回溯 path.pop_back(); // 回溯 -}if (cur-right) {path -;traversal(cur-right, path, result); // 右path.pop_back(); // 回溯path.pop_back(); // 回溯 -}}public:vectorstring binaryTreePaths(TreeNode* root) {vectorstring result;string path;if (root NULL) return result;traversal(root, path, result);return result;}
};
大家应该可以感受出来如果把 path - 作为函数参数就是可以的因为并没有改变path的数值执行完递归函数之后path依然是之前的数值相当于回溯了
综合以上第二种递归的代码虽然精简但把很多重要的点隐藏在了代码细节里第一种递归写法虽然代码多一些但是把每一个逻辑处理都完整的展现出来了。
#拓展
这里讲解本题解的写法逻辑以及一些更具体的细节下面的讲解中涉及到C语法特性如果不是C的录友就可以不看了避免越看越晕。
如果是C的录友建议本题独立刷过两遍再看下面的讲解同样避免越看越晕造成不必要的负担。
在第二版本的代码中其实仅仅是回溯了 - 部分调用两次pop_back一个pop 一次pop-大家应该疑惑那么 path to_string(cur-val); 这一步为什么没有回溯呢 一条路径能持续加节点 不做回溯吗
其实关键还在于 参数使用的是 string path这里并没有加上引用 即本层递归中path 该节点数值但该层递归结束上一层path的数值并不会受到任何影响。 如图所示
节点4 的path在遍历到节点3path3遍历节点3的递归结束之后返回节点4回溯的过程path并不会把3加上。
所以这是参数中不带引用不做地址拷贝只做内容拷贝的效果。这里涉及到C引用方面的知识
在第一个版本中函数参数我就使用了引用即 vectorint path 这是会拷贝地址的所以 本层递归逻辑如果有path.push_back(cur-val); 就一定要有对应的 path.pop_back()
那有同学可能想为什么不去定义一个 string path 这样的函数参数呢然后也可能在递归函数中展现回溯的过程但关键在于path to_string(cur-val); 每次是加上一个数字这个数字如果是个位数那好说就调用一次path.pop_back()但如果是 十位数百位数千位数呢 百位数就要调用三次path.pop_back()才能实现对应的回溯操作这样代码实现就太冗余了。
所以第一个代码版本中我才使用 vector 类型的path这样方便给大家演示代码中回溯的操作。 vector类型的path不管 每次 路径收集的数字是几位数总之一定是int所以就一次 pop_back就可以。
#迭代法
至于非递归的方式我们可以依然可以使用前序遍历的迭代方式来模拟遍历路径的过程对该迭代方式不了解的同学可以看文章二叉树听说递归能做的栈也能做 **(opens new window)** 和二叉树前中后序迭代方式统一写法 **(opens new window)** 。
这里除了模拟递归需要一个栈同时还需要一个栈来存放对应的遍历路径。
C代码如下
class Solution {
public:vectorstring binaryTreePaths(TreeNode* root) {stackTreeNode* treeSt;// 保存树的遍历节点stackstring pathSt; // 保存遍历路径的节点vectorstring result; // 保存最终路径集合if (root NULL) return result;treeSt.push(root);pathSt.push(to_string(root-val));while (!treeSt.empty()) {TreeNode* node treeSt.top(); treeSt.pop(); // 取出节点 中string path pathSt.top();pathSt.pop(); // 取出该节点对应的路径if (node-left NULL node-right NULL) { // 遇到叶子节点result.push_back(path);}if (node-right) { // 右treeSt.push(node-right);pathSt.push(path - to_string(node-right-val));}if (node-left) { // 左treeSt.push(node-left);pathSt.push(path - to_string(node-left-val));}}return result;}
};当然使用java的同学可以直接定义一个成员变量为object的栈StackObject stack new Stack();这样就不用定义两个栈了都放到一个栈里就可以了。
#总结
本文我们开始初步涉及到了回溯很多同学过了这道题目可能都不知道自己其实使用了回溯回溯和递归都是相伴相生的。
我在第一版递归代码中把递归与回溯的细节都充分的展现了出来大家可以自己感受一下。
第二版递归代码对于初学者其实非常不友好代码看上去简单但是隐藏细节于无形。
最后我依然给出了迭代法。
对于本题充分了解递归与回溯的过程之后有精力的同学可以再去实现迭代法。 周一
本周刚开始我们讲解了判断二叉树是否对称的写法 二叉树我对称么 **(opens new window)** 。
这道题目的本质是要比较两个树这两个树是根节点的左右子树遍历两棵树而且要比较内侧和外侧节点所以准确的来说是一个树的遍历顺序是左右中一个树的遍历顺序是右左中。
而本题的迭代法中我们使用了队列需要注意的是这不是层序遍历而且仅仅通过一个容器来成对的存放我们要比较的元素认识到这一点之后就发现用队列用栈甚至用数组都是可以的。
那么做完本题之后再看如下两个题目。
100.相同的树(opens new window)572.另一个树的子树(opens new window)
二叉树我对称么 ****(opens new window)****中的递归法和迭代法只需要稍作修改其中一个树的遍历顺序便可刷了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-left); // 左子树左、 右子树左 相对于求对称二叉树只需改一下这里的顺序bool inside compare(left-right, right-right); // 左子树右、 右子树右bool isSame outside inside; // 左子树中、 右子树中 逻辑处理return isSame;}bool isSymmetric(TreeNode* p, TreeNode* q) {return compare(p, q);}
};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.相同的树迭代法代码如下
class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {if (p NULL q NULL) return true;if (p NULL || q NULL) return false;queueTreeNode* 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了。
#周二
在二叉树看看这些树的最大深度 **(opens new window)** 中我们讲解了如何求二叉树的最大深度。
本题可以使用前序也可以使用后序遍历左右中使用前序求的就是深度使用后序呢求的是高度。
而根节点的高度就是二叉树的最大深度所以本题中我们通过后序求的根节点高度来求的二叉树最大深度所以二叉树看看这些树的最大深度 **(opens new window)** 中使用的是后序遍历。
本题当然也可以使用前序代码如下(充分表现出求深度回溯的过程)
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; // 深度1getDepth(node-left, depth);depth--; // 回溯深度-1}if (node-right) { // 右depth; // 深度1getDepth(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;}
};#周三
在二叉树看看这些树的最小深度 **(opens new window)** 中我们讲解如何求二叉树的最小深度 这道题目要是稍不留心很容易犯错。
注意这里最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。
什么是叶子节点左右孩子都为空的节点才是叶子节点
求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
注意到这一点之后 递归法和迭代法 都可以参照二叉树看看这些树的最大深度 **(opens new window)** 写出来。
#周四
我们在二叉树我有多少个节点 **(opens new window)** 中讲解了如何求二叉树的节点数量。
这一天是十一长假的第一天又是双节所以简单一些只要把之前两篇二叉树看看这些树的最大深度 **(opens new window)** 二叉树看看这些树的最小深度 **(opens new window)** 都认真看了的话这道题目可以分分钟刷掉了。
估计此时大家对这一类求二叉树节点数量以及求深度应该非常熟练了。
#周五
在二叉树我平衡么 **(opens new window)** 中讲解了如何判断二叉树是否是平衡二叉树
今天讲解一道判断平衡二叉树的题目其实 方法上我们之前讲解深度的时候都讲过了但是这次我们通过这道题目彻底搞清楚二叉树高度与深度的问题以及对应的遍历方式。
二叉树节点的深度指从根节点到该节点的最长简单路径边的条数。 二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数。
但leetcode中强调的深度和高度很明显是按照节点来计算的。
关于根节点的深度究竟是1 还是 0不同的地方有不一样的标准leetcode的题目中都是以节点为一度即根节点深度是1。但维基百科上定义用边为一度即根节点的深度是0我们暂时以leetcode为准毕竟要在这上面刷题。
当然此题用迭代法其实效率很低因为没有很好的模拟回溯的过程所以迭代法有很多重复的计算。
虽然理论上所有的递归都可以用迭代来实现但是有的场景难度可能比较大。
例如都知道回溯法其实就是递归但是很少人用迭代的方式去实现回溯算法
讲了这么多二叉树题目的迭代法有的同学会疑惑迭代法中究竟什么时候用队列什么时候用栈
如果是模拟前中后序遍历就用栈如果是适合层序遍历就用队列当然还是其他情况那么就是 先用队列试试行不行不行就用栈。
#周六
在二叉树找我的所有路径 **(opens new window)** 中正式涉及到了回溯很多同学过了这道题目可能都不知道自己使用了回溯其实回溯和递归都是相伴相生的。最后我依然给出了迭代法的版本。
我在题解中第一个版本的代码会把回溯的过程充分体现出来如果大家直接看简洁的代码版本很可能就会忽略的回溯的存在。
我在文中也强调了这一点。
有的同学还不理解 文中精简之后的递归代码回溯究竟隐藏在哪里了。
文中我明确的说了回溯就隐藏在traversal(cur-left, path -, result);中的 path -。 每次函数调用完path依然是没有加上- 的这就是回溯了。
如果还不理解的话可以把
traversal(cur-left, path -, result);改成
string tmp path -;
traversal(cur-left, tmp, result);看看还行不行了答案是这么写就不行了因为没有回溯了。
#总结
二叉树的题目我都是使用了递归三部曲一步一步的把整个过程分析出来而不是上来就给出简洁的代码。
一些同学可能上来就能写出代码大体上也知道是为啥可以自圆其说但往细节一扣就不知道了。
所以刚接触二叉树的同学建议按照文章分析的步骤一步一步来不要上来就照着精简的代码写那样写完了也很容易忘的知其然不知其所以然。
简短的代码看不出遍历的顺序也看不出分析的逻辑还会把必要的回溯的逻辑隐藏了所以尽量按照原理分析一步一步来写出来之后再去优化代码。
大家加个油 相信很多小伙伴刷题的时候面对力扣上近两千道题目感觉无从下手我花费半年时间整理了Github项目「力扣刷题攻略」https://github.com/youngyangyang04/leetcode-master ****(opens new window)**** 。 里面有100多道经典算法题目刷题顺序、配有40w字的详细图解常用算法模板总结以及难点视频讲解按照list一道一道刷就可以了star支持一波吧 公众号代码随想录(opens new window)B站代码随想录(opens new window)Githubleetcode-master(opens new window)知乎代码随想录(opens new window)
404.左叶子之和
力扣题目链接(opens new window)
计算给定二叉树的所有左叶子之和。
示例
#算法公开课
《代码随想录》算法视频公开课 ****(opens new window)**** 二叉树的题目中总有一些规则让你找不到北 | LeetCode404.左叶子之和 ****(opens new window)**** 相信结合视频在看本篇题解更有助于大家对本题的理解。
#思路
首先要注意是判断左叶子不是二叉树左侧节点所以不要上来想着层序遍历。
因为题目中其实没有说清楚左叶子究竟是什么节点那么我来给出左叶子的明确定义节点A的左孩子不为空且左孩子的左右孩子都为空说明是叶子节点那么A节点的左孩子为左叶子节点
大家思考一下如下图中二叉树左叶子之和究竟是多少
其实是0因为这棵树根本没有左叶子
但看这个图的左叶子之和是多少
相信通过这两个图大家对最左叶子的定义有明确理解了。
那么判断当前节点是不是左叶子是无法判断的必须要通过节点的父节点来判断其左孩子是不是左叶子。
如果该节点的左节点不为空该节点的左节点的左节点为空该节点的左节点的右节点为空则找到了一个左叶子判断代码如下
if (node-left ! NULL node-left-left NULL node-left-right NULL) {左叶子节点处理逻辑
}#递归法
递归的遍历顺序为后序遍历左右中是因为要通过递归函数的返回值来累加求取左叶子数值之和。
递归三部曲
确定递归函数的参数和返回值
判断一个树的左叶子节点之和那么一定要传入树的根节点递归函数的返回值为数值之和所以为int
使用题目中给出的函数就可以了。
确定终止条件
如果遍历到空节点那么左叶子值一定是0
if (root NULL) return 0;注意只有当前遍历的节点是父节点才能判断其子节点是不是左叶子。 所以如果当前遍历的节点是叶子节点那其左叶子也必定是0那么终止条件为
if (root NULL) return 0;
if (root-left NULL root-right NULL) return 0; //其实这个也可以不写如果不写不影响结果但就会让递归多进行了一层。确定单层递归的逻辑
当遇到左叶子节点的时候记录数值然后通过递归求取左子树左叶子之和和 右子树左叶子之和相加便是整个树的左叶子之和。
代码如下
int leftValue sumOfLeftLeaves(root-left); // 左
if (root-left !root-left-left !root-left-right) {leftValue root-left-val;
}
int rightValue sumOfLeftLeaves(root-right); // 右int sum leftValue rightValue; // 中
return sum;整体递归代码如下
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if (root NULL) return 0;if (root-left NULL root-right NULL) return 0;int leftValue sumOfLeftLeaves(root-left); // 左if (root-left !root-left-left !root-left-right) { // 左子树就是一个左叶子的情况leftValue root-left-val;}int rightValue sumOfLeftLeaves(root-right); // 右int sum leftValue rightValue; // 中return sum;}
};以上代码精简之后如下
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if (root NULL) return 0;int leftValue 0;if (root-left ! NULL root-left-left NULL root-left-right NULL) {leftValue root-left-val;}return leftValue sumOfLeftLeaves(root-left) sumOfLeftLeaves(root-right);}
};精简之后的代码其实看不出来用的是什么遍历方式了对于算法初学者以上根据第一个版本来学习。
#迭代法
本题迭代法使用前中后序都是可以的只要把左叶子节点统计出来就可以了那么参考文章 二叉树听说递归能做的栈也能做 **(opens new window)** 和二叉树迭代法统一写法 **(opens new window)** 中的写法可以写出一个前序遍历的迭代法。
判断条件都是一样的代码如下 class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {stackTreeNode* st;if (root NULL) return 0;st.push(root);int result 0;while (!st.empty()) {TreeNode* node st.top();st.pop();if (node-left ! NULL node-left-left NULL node-left-right NULL) {result node-left-val;}if (node-right) st.push(node-right);if (node-left) st.push(node-left);}return result;}
};#总结
这道题目要求左叶子之和其实是比较绕的因为不能判断本节点是不是左叶子节点。
此时就要通过节点的父节点来判断其左孩子是不是左叶子了。
平时我们解二叉树的题目时已经习惯了通过节点的左右孩子判断本节点的属性而本题我们要通过节点的父节点判断本节点的属性。
希望通过这道题目可以扩展大家对二叉树的解题思路。
