如何做百度站长绑定网站,网站诊断报告案例,网站开发入门教程,wordpress 搜索摘要文章目录 1. 前言2. 算法题2331.计算布尔二叉树的值129.求根节点到叶节点数字之和LCR047.二叉树剪枝98.验证二叉搜索树230.二叉搜索树中第K小的元素257.二叉树的所有路径 1. 前言
有关 递归 的相关解释与解题 请看下文#xff1a; 以汉诺塔理解递归、并用递归解决算法题 对于… 文章目录 1. 前言2. 算法题2331.计算布尔二叉树的值129.求根节点到叶节点数字之和LCR047.二叉树剪枝98.验证二叉搜索树230.二叉搜索树中第K小的元素257.二叉树的所有路径 1. 前言
有关 递归 的相关解释与解题 请看下文 以汉诺塔理解递归、并用递归解决算法题 对于二叉树我们曾学过前序遍历其就是深度优先搜索的一种应用。 在二叉树的前序遍历中我们首先访问根节点然后递归对左子树进行前序遍历最后递归地对右子树进行前序遍历。 在深度优先搜索算法中我们从起始节点开始递归地探索每个可达节点直到没有未访问的相邻节点为止。因此前序遍历也可以看作是对图或树进行深度优先搜索的一种方式。它遵循先访问根节点然后递归地访问左子节点和右子节点的顺序。
2. 算法题
2331.计算布尔二叉树的值 思路
题意分析对于叶子节点有falstrue对于非叶子节点有|、要求算出最终结果我们只需要进行深搜遍历一遍二叉树即可。解法递归dfs 前序遍历 函数体即前序遍历分别用bool类型记录左右子树值返回值当前节点非叶子节点根据其值判断将左右子树 或还是与函数出口即递归出口当遍历到叶子节点后通过其值向上返回bool类型。
代码
bool evaluateTree(TreeNode* root) {// 递归// 叶子节点为终止条件if(root-left nullptr root-right nullptr)return root-val 1 ? true : false;bool left evaluateTree(root-left);bool right evaluateTree(root-right);return root-val 2 ? left | right : left right;
}129.求根节点到叶节点数字之和 思路
题目要求计算二叉树中所有根节点到叶子节点的路径和如示例所示对于[1, 2, 3]的最终结果就是两条路径 12 13 25解法递归dfs 思路如上图所示以此我们可以完成dfs函数 函数头需要接收一个节点以及到该节点时的路径值且最终返回的也是总的路径值即int dfs(Node* root, int preSum)函数体先统计到当前节点的路径值再进行左右子树的遍历终止条件当遍历到叶子节点向上返回值
代码
class Solution {
public:// 返回到当前节点计算的所有值int dfs(TreeNode* root, int prevSum) {// 1. 计算prevSum和该节点的数字和int sum prevSum*10 root-val;// 2. 终止条件叶子节点 if(!root-left !root-right) return sum;// 3.递归左右子树int left root-left ? dfs(root-left, sum) : 0;int right root-right ? dfs(root-right, sum) : 0;// 4. 计算出左右子树和并向上返回return left right;}int sumNumbers(TreeNode* root) {if(!root) return 0;// 递归return dfs(root, 0);}
};LCR047.二叉树剪枝 思路
题意分析题目要求删除二叉树中所有不包含1的子树则可以利用递归从后向前进行删除。即通过后序遍历 删除值为0的叶子节点解法递归dfs 后序遍历 函数体后续遍历当遇到值为0的叶子节点将该节点值设为空函数出口当遍历到空指针时向上返回。
代码
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 !root-right root-val 0) {// delete root; // 释放内存防止内存泄漏root nullptr; // 置空}return root;}
};98.验证二叉搜索树 思路
题意分析题目要求验证一棵树是否是二叉搜索树。解法递归dfs 中序遍历 利用二叉搜索树性质 而我们知道根据二叉搜索树的定义其中序遍历是有序的对于BSTree的任意一个节点其前驱节点一定小于自身 据此我们可以利用中序遍历以及该性质解题 定义 前驱节点以及一个标记符flag用于标记当前节点是否满足条件。函数体中序遍历对于当前节点判断如果其前驱节点存在且大于自身则不是BSTree将标记符设为false递归结束。结束条件当遍历到空节点或标记符为false时向上返回
代码
class Solution {
public:TreeNode* prev nullptr; // 定义全局变量用于找前驱节点bool flag true;; // 标记树是否是bstree bool isValidBST(TreeNode* root) {// 递归if(root ! nullptr flag){// 中序遍历isValidBST(root-left);// 如果前一个节点的值大于当前节点的值则不满足二叉排序树的条件if(prev ! nullptr prev-val root-val)flag false;prev root; // 更新前驱节点isValidBST(root-right);}return flag;}
};230.二叉搜索树中第K小的元素 思路
题意分析题目要求找到二叉搜索树的倒数第k个最小元素依照上题的思路进行中序遍历即可。解法递归dfs 中序遍历 利用二叉搜索树性质 定义全局变量省去多次递归创建变量的开销定义count和ret分别记录k值和结果值dfs函数中进行中序遍历每次递归–count直到count0此时节点的值就是ret
代码
class Solution {
public:// 全局变量解决递归问题int count, ret;void dfs(TreeNode* root) {// 中序遍历if(!root || count 0) return;dfs(root-left);--count;if(count 0)ret root-val;dfs(root-right);}int kthSmallest(TreeNode* root, int k) {count k;dfs(root);return ret;}
};257.二叉树的所有路径 思路
题意分析输出所有从根节点到叶子节点的路径。思路思路很简单就是直接使用前序遍历即可对每个节点都加入到字符串中并对字符串后加箭头。解法递归dfs 前序遍历 细节问题 叶子节点不需要加箭头写代码时另外列出其余则是对vector和string的使用
代码
class Solution {
public:vectorstring ret; // 最终结果// 如果将path定义为全局变量则需要手动恢复现场// 而作为函数参数则由函数的性质自动完成了此过程void dfs(TreeNode* root, string path) {// 前序遍历if(root nullptr) return;// 叶子结点不需要箭头// 将其加入到ret中并返回if(!root-left !root-right){path to_string(root-val);ret.push_back(path);return;}path to_string(root-val) -;dfs(root-left, path);dfs(root-right, path);}vectorstring binaryTreePaths(TreeNode* root) {string path ; // 用于记录当前路径dfs(root, path);return ret;}
};
