💕"什么样的灵魂就要什么样的养料，越悲怆的时候我越想嬉皮。"💕
作者：Mylvzi
文章主要内容：算法系列–递归(2)
前言:今天带来的是
算法系列--递归(2)的讲解,包含六个和二叉树相关的题目哦
1.计算布尔⼆叉树的值
链接: https://leetcode.cn/problems/evaluate-boolean-binary-tree/
分析:
- 函数头:传入节点,得到左右子树的值, boolean dfs(TreeNode root)
- 函数体:dfs(root.left); dfs(root.right)
- 递归出口:当遇到叶子结点的时候直接返回即可
代码:
class Solution { public boolean evaluateTree(TreeNode root) {// 函数头就是这样 if(root.left == null) return root.val == 0 ? false : true; boolean left = evaluateTree(root.left);// 得到左子树的值 boolean right = evaluateTree(root.right);// 得到右子树的值 return root.val == 2 ? left | right : left & right;// 判断 } }
2.求根节点到叶节点数字之和
链接: https://leetcode.cn/problems/sum-root-to-leaf-numbers/
分析:
代码:
class Solution { public int sumNumbers(TreeNode root) { return dfs(root,0); } private int dfs(TreeNode root, int presum) { // 1.计算当前节点的值 presum = presum * 10 + root.val; // 递归出口 if(root.left == null && root.right == null) return presum; // 2.递归左子树 int ret = 0; if(root.left != null) ret += dfs(root.left,presum); // 3.递归右子树 if(root.right != null) ret += dfs(root.right,presum); // 4.返回左右子树的总和 return ret; } }
总结:
当一个递归函数不好想时,就去模拟一遍整个过程
比如本题,你要想想这个接口是干啥的,你想要这个接口帮你做什么–给接口一个根节点,你去给我算出左右子树的和,并且返回给我,那么就能确定出函数头;
- 返回值:int类型,
左子树 + 右子树的和 - 函数名:
dfs - 参数:
root,还要给我走到当前节点的值,我只有知道这个值,才能和子节点相连
3.⼆叉树剪枝
链接: https://leetcode.cn/problems/binary-tree-pruning/description/
分析:
- 明确接口的作用:给你一个根节点root,你去给我判断左右子树是否满足剪枝的条件,如果满足就
断开和根节点的连接,如果不满足继续保持连接即可 - 函数头:返回值应该是
TreeNode,当条件满足时,需要断开连接,直接返回null就可以实现,如果条件不满足,还是需要返回子根节点;函数名dfs,参数需要通过一个根节点就行 - 函数体:先分别遍历左右子树,更新root的左右子树的连接条件,接着判断是否满足剪枝的条件,如果满足,返回null,表示需要剪枝,如果不满足,返回当前的根节点即可
- 递归出口:当节点为空时,直接返回null
代码:
class Solution { public TreeNode pruneTree(TreeNode root) { return dfs(root); } private TreeNode dfs(TreeNode root) { if(root == null) return null;// 递归出口 root.left = dfs(root.left);// 遍历左子树 root.right = dfs(root.right);// 遍历右子树 if(root.left == null && root.right == null && root.val == 0) // 条件满足将root置为空 return null; else return root; } }
算法系列--递归(2)--二叉树专题（下）https://developer.aliyun.com/article/1480798?spm=a2c6h.13148508.setting.30.361f4f0eyTL4lb
