西安微信网站建设公司,怀化公司做网站,泰安放心的企业建站公司,wordpress优化图片分离代码随想录Day 17 | 110 平衡二叉树 257 二叉树的所有路径 404 左叶子之和 平衡二叉树二叉树的所有路径左叶子之和 平衡二叉树 文档讲解#xff1a;代码随想录 视频讲解#xff1a; 后序遍历求高度#xff0c;高度判断是否平衡 | LeetCode#xff1a;110.平衡二叉树 状态 … 代码随想录Day 17 | 110 平衡二叉树 257 二叉树的所有路径 404 左叶子之和 平衡二叉树二叉树的所有路径左叶子之和 平衡二叉树 文档讲解代码随想录 视频讲解 后序遍历求高度高度判断是否平衡 | LeetCode110.平衡二叉树 状态 左右子树的高度差不大于1高度就采用后序遍历同样使用递归的解法
终止条件当前节点为空时 就返回0函数参数树的所有节点返回值树的高度或者失效标记单层递归功能函数在一个父节点的位置我们需要做一件事一个是判断当前父节点的左右子树是不是高度差小于等于1如果是那么就可以返回当前这个节点的高度给它的父节点。如果不是说明已经不是AVL树了这时候就需要一个标记来说明然后返回这个标记给其父节点。当父节点接受到这个标记就知道已经不是AVL那么后面的求父节点的高度也不需要做了直接继续返回标记
class Solution {public:int IsAVL(TreeNode* root){//终止条件if(root nullptr) return 0;//后序遍历//左节点int left IsAVL(root-left);//如果得到-1的返回说明其子树中已经不满足则直接返回-1if(left -1) return -1;//右节点int right IsAVL(root-right);if(right -1) return -1;//单层递归//判断左右子树的高度差if(abs(left-right) 1){return -1;}return 1max(left,right);}
public:bool isBalanced(TreeNode* root) {int res IsAVL(root);if(res -1) return false;return true;}
};利用层序遍历的迭代法对每个节点进行层序遍历那么求得的就是以该节点为根节点的子树深度同样也是高度。所以我们可以先定义一个求取深度的函数然后同样利用层序遍历对每个节点的左右子节点调用这个函数然后来比较深度差值。
class Solution {public:int GetDep(TreeNode* cur){queueTreeNode* treeque;if(cur) treeque.push(cur);int dep 0;while(!treeque.empty()){int tempsize treeque.size();for(int i 0;itempsize;i){TreeNode* temp treeque.front();treeque.pop();if(temp-left) treeque.push(temp-left);if(temp-right) treeque.push(temp-right);}dep;}return dep;}
public:bool isBalanced(TreeNode* root) {queueTreeNode* treeque;if(root) treeque.push(root);while(!treeque .empty()){int tempsize treeque.size();for(int i0;itempsize;i){TreeNode* cur treeque.front();int left GetDep(cur-left);int right GetDep(cur-right);if(abs(left-right) 1){return false;}treeque.pop();if(cur-left) treeque.push(cur-left);if(cur-right) treeque.push(cur-right);}}return true;}
};二叉树的所有路径 文档讲解代码随想录 视频讲解 递归中带着回溯你感受到了没| LeetCode257. 二叉树的所有路径 状态× 从根节点开始到一个叶子节点的路径采用前序遍历当寻找到一条路径还需要回退到上一个岔路口选择另一条路进行遍历找到其他的路径直到所找到的出口是最右边的叶子节点。 递归的三个要素
参数和返回值节点当前的这条路径的所有节点组成的数组path最终存储结果的数组res循环终止条件当当前节点的左节点和右节点为空时说明该节点是叶子节点就说明当前这条路径到头了。 当到达终止条件时就应该处理当前字符串的结果了这时候我们就需要将path中的所有节点值变为字符存入res中单层递归 递归加回溯递归和回溯不能分开首先是对中节点的操作就是直接压入path数组中对于左节点和右节点分别调用递归如果存在的话。调用递归之后还需要回溯
if (cur-left) {traversal(cur-left, path, result);path.pop_back(); // 回溯
}
if (cur-right) {traversal(cur-right, path, result);path.pop_back(); // 回溯
}具体代码
/*** 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:void GetPath(TreeNode* root, vectorint path, vectorstring res){//中节点操作先操作中节点是为了叶子节点成为中节点是的加入pathpath.push_back(root-val);if(root-left nullptr root-right nullptr){string temp;for(int i0;ipath.size()-1;i){temp to_string(path[i]);temp -;}temp to_string(path[path.size()-1]);res.push_back(temp);return ;}//递归左右回溯if(root-left){GetPath(root-left,path,res);//回溯到父节点 即岔路口//path.pop_back();}if(root-right){GetPath(root-right,path,res);//path.pop_back();}}
public:vectorstring binaryTreePaths(TreeNode* root) {vectorint temp;vectorstring res;GetPath(root, temp, res);return res;}
};回溯的目的主要要是保证当前节点的数组统计保持不变这样在向回递归时可以保持在节点处所以如果对于传入函数的参数是值传入那么其实就可以不需要使用回溯。因为对path的修改只是对临时变量的修改并不会改变函数外部的path相当于用语法特性来完成了回溯。如果是按指针或者引用传递那么就会对函数外部的path修改为了保持当前节点的path不变需要手动回溯
左叶子之和 文档讲解代码随想录 视频讲解 二叉树的题目中总有一些规则让你找不到北 | LeetCode404.左叶子之和 状态 递归三要素
返回值和参数我采用了没有返回值参数为节点和最终求和的值这两个参数终止条件当前节点为空因为左或者右叶子节点的判断只能通过父节点来判断单层递归逻辑当前父节点中用来存储其子树的左叶子节点和对于存在左右子节点那么就继续递归调用。
class Solution {void GetLeft(TreeNode* root, int sum){if(root nullptr) return ;//对左节点的递归if(root-left){GetLeft(root-left,sum); }//对右节点的递归if(root-right){GetLeft(root-right,sum);}//对中节点的计算if(root-left !nullptr root-left-left nullptr root-left-right nullptr){sum root-left-val;}}
public:int sumOfLeftLeaves(TreeNode* root) {int sum 0;GetLeft(root,sum);return sum;}
};采用的是左右中的顺序
采用层序遍历 对弹出的节点判断其是否有左叶子节点如果是就加入
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {queueTreeNode* treeque;if(root) treeque.push(root);int sum 0;while(!treeque.empty()){int tempsize treeque.size();for(int i0;itempsize;i){TreeNode* cur treeque.front();treeque.pop();if(cur-left ! nullptr cur-left-left nullptr cur-left-right nullptr){sum cur-left-val;}if(cur-left) treeque.push(cur-left);if(cur-right) treeque.push(cur-right);}}return sum;}
};
