wordpress建站教程linux,设计网站建设合同书,网站建设ppt演示文稿,微信上浏览自己做的网站吗二叉树剪枝
LCR 047. 二叉树剪枝 - 力扣#xff08;LeetCode#xff09; 本题要求我们将全部为0的二叉树去掉#xff0c;也就是剪枝#xff0c;当我们举一个具体的例子进行模拟时#xff0c;会发现#xff0c;只关注于对其中一个子树的根节点进行剪枝#xff0c;由于我… 二叉树剪枝
LCR 047. 二叉树剪枝 - 力扣LeetCode 本题要求我们将全部为0的二叉树去掉也就是剪枝当我们举一个具体的例子进行模拟时会发现只关注于对其中一个子树的根节点进行剪枝由于我们只去掉所有节点都是0的子树所以需要先判断它的左子树是否被去掉右子树是否被去掉最后再判断根节点本身的值是否为0如果这三个条件全部满足我们需要告诉这个子树的父亲该子树被去掉了。 通过上面的分析不难发现这个递归函数的传入参数只需要一个根节点的指针并且该函数需要把剪枝的结果传给父亲所以递归函数需要一个返回值。
/*** 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:TreeNode* pruneTree(TreeNode* root) {if(root nullptr) return nullptr;root-left pruneTree(root-left);root-right pruneTree(root-right);if(root-left nullptr root-right nullptr root-val 0) {delete root;root nullptr;}return root;}
}; 验证二叉搜索树
98. 验证二叉搜索树 - 力扣LeetCode 关于二叉搜索树有一个简单的性质就是二叉搜索树的中序遍历序列是有序的。所以我们可以根据这个性质来验证一个二叉树是否为二叉搜索树当然我指的并不是创建一个数组进行判断而是递归实现二叉树的中序遍历并在这个过程中去判断是否满足性质。 我们之所以要根据中序遍历序列来判断而不是简单地递归判断左节点小于根节点小于右节点是因为满足这个性质的不一定是二叉搜索树 说回正题那我们要怎么确定二叉树的中序遍历序列呢实际上我们可以定义一个全局变量prev来充当遍历的“指针”那么中序遍历过程中我们只需要满足根节点的值大于prev就能确保满足二叉搜索树的性质。 目前的思路已经能够完成这道题目了但是我们现在就相当于老老实实地把整个二叉树遍历一遍返回结果。但是只要我们发现左子树或者中间节点不符合二叉搜索树性质就可以直接返回结果了因为这注定不可能是二叉搜索树了。而这个操作其实就是剪枝。
class Solution {
public:long prev LONG_MIN;bool isValidBST(TreeNode* root) {if(root nullptr) return true;// 判断左子树是否满足二叉搜索树性质bool left isValidBST(root-left);if(!left) return false; // 剪枝// 判断当前节点是否满足性质bool cur false;if(root-val prev)cur true;if(!cur) return false; // 剪枝// 更新prev值prev root-val;// 判断右子树是否满足二叉搜索树性质bool right isValidBST(root-right);return left right cur;}
};
二叉树的所有路径
257. 二叉树的所有路径 - 力扣LeetCode 依据题意我们需要把二叉树的所有从根节点到叶子节点的路径找出来这显然就是个深度优先遍历问题dfs因为存在这样的情况遍历到左边的叶子节点后得到一个字符串后进行回溯再遍历右边的叶子节点得到另一个字符串。所以我们需要想办法能对字符串进行回溯。 我们举一两个例子进行模拟就能发现遍历二叉树的方式应为前序遍历也就是先将根节点的值加入字符串然后分别处理左子树和右子树。因为我们需要返回所有得到的字符串所以可以定义一个全局的字符串数组又因为我们需要得到从根节点到叶子的路径所以递归函数还需要传入当前已经遍历的路径。 至于前面提到的回溯其实只要递归函数传字符串的值而不是引用就行了这样的话遍历完左子树将左子树的路径加入字符串数组由于不改变已经遍历的路径再去遍历右子树就相当于实现了回溯。
class Solution {
public:vectorstring ret;void dfs(TreeNode* root, string path){if(root-left nullptr root-right nullptr) {path to_string(root-val);ret.push_back(path);return;}path to_string(root-val) -;if(root-left) dfs(root-left, path);if(root-right) dfs(root-right, path);}vectorstring binaryTreePaths(TreeNode* root) {string path;dfs(root, path);return ret;}
};
全排列
46. 全排列 - 力扣LeetCode 对于这种枚举类型的题目我们首先要做的就是画出决策树然后根据决策树进行递归代码的编写。题目要求我们返回所有满足条件的数组我们如果让递归函数来传这些变量不但存在开销代码编写也会变得复杂所以可以直接定义全局变量省去考虑各种情况的麻烦。 关于全局变量的定义首先肯定是一个二维数组ret存所有排列的可能情况又因为枚举过程中我们可能需要经常进行回溯所以把存放排列顺序的数组path也定义为全局变量最后因为我们的决策树需要进行剪枝所以为了方便判断是否剪枝可以再定义bool类型的数组check表示当前访问的节点是否已经被遍历。 递归函数的编写我们只需要考虑当前节点要干什么遍历check数组判断是否遍历各子树如果需要遍历则将子节点值添加到path数组将当前位置的check设为true然后递归调用自己返回后进行回溯将子节点从path移除重新将check设为false. 最后是递归出口当path的大小和nums的大小一样时说明已经是一个完整的序列可以将path添加到ret后返回。 class Solution {
public:vectorvectorint ret;vectorint path;bool check[7];void dfs(vectorint nums){if(path.size() nums.size()){ret.push_back(path);return ;}for(int i 0; i nums.size(); i){if(check[i] false){path.push_back(nums[i]);check[i] true;dfs(nums);path.pop_back();check[i] false;}}}vectorvectorint permute(vectorint nums) {dfs(nums);return ret;}
} ;
