算法系列--递归(2)--二叉树专题（上）
https://developer.aliyun.com/article/1480794?spm=a2c6h.13148508.setting.14.5f4e4f0ek1txt6
💕"什么样的灵魂就要什么样的养料，越悲怆的时候我越想嬉皮。"💕
作者：Mylvzi
文章主要内容：算法系列–递归(2)
前言:今天带来的是
算法系列--递归(2)的讲解,包含六个和二叉树相关的题目哦
4. 验证⼆叉搜索树
链接: https://leetcode.cn/problems/validate-binary-search-tree/description/
分析:
本题要利用到二叉搜索树的一个性质–二叉搜索树的中序遍历的结果是一个有序序列
- 明确接口的作用:给你一个根节点,你去给我判断一下左右子树是否都符合二叉搜索树的条件,如果不满足直接返回false,满足返回true
- 函数头:返回值是boolean,参数需要提供一个根节点,函数名是dfs
- 函数体:由于要中序遍历,所以应该先遍历左子树,判断左子树是否满足二叉搜索树,如果不满足,直接返回false即可(此时就没有遍历根节点和右子树的必要了),如果满足,判断当前根节点的状态是否满足二叉搜索树,具体的判断条件就是比较
root.val和prev值的大小,如果root.val < prev,则不符合二叉搜索树的条件,直接返回false,如果root.val > prev,则符合二叉搜索树的条件,继续判断右子树是否符合条件,如果右子树满足,返回true,如果不满足,返回false - 递归出口:当节点为空时,返回true
代码:
class Solution { // 二叉搜索树的性质:中序遍历的结果是一个有序的序列 long prev = Long.MIN_VALUE;// 设置为long是为了防止越界 public boolean isValidBST(TreeNode root) { if(root == null) return true;// 空树也是二叉搜索树 boolean left = isValidBST(root.left); if(left == false) return false;// 剪枝 boolean cur = root.val > prev ? true : false; if(cur == false) return false;// 剪枝 prev = root.val;// 更新prev boolean right = isValidBST(root.right); return right; } }
5.⼆叉搜索树中第 k ⼩的元素
链接: https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/
分析:
本题还是利用二叉搜索树的性质:二叉搜索树的中序遍历的结果是一个有序序列
设计一个ret作为返回值,设计一个cnt计数器,让cnt的初始值为k,通过中序遍历,每遍历到一个节点就让cnt--,当cnt = 0是,将ret更新为cur.val,然后返回即可
代码:
class Solution { int cnt; int ret; public int kthSmallest(TreeNode root, int k) { cnt = k; dfs(root); return ret; } private void dfs(TreeNode root) { if(root == null || cnt == 0) return; dfs(root.left); cnt--; if(cnt == 0) ret = root.val; dfs(root.right); } }
6.⼆叉树的所有路径
链接: https://leetcode.cn/problems/binary-tree-paths/
分析:
- 明确接口的作用:给你一个根节点,给我拼接上左子树和右子树
- 函数头: 需要提供一个根节点和走到当前节点之前已经拼接好的字符串(path)
- 函数体:先创建出一个新的字符串用于接受path,接着以这个新的字符串为基准,遍历左子树和右子树
- 递归出口:当root为叶子节点时,证明一个完整的二叉树路径已经被拼接完毕,让ret添加这个拼接完毕的字符串路径即可
代码:
class Solution { List<String> ret = new ArrayList<>();// 返回值 public List<String> binaryTreePaths(TreeNode root) { dfs(root,new StringBuffer()); return ret; } private void dfs(TreeNode root,StringBuffer path) { StringBuffer newPath = new StringBuffer(path); newPath.append(Integer.toString(root.val)); if(root.left == null && root.right == null) { ret.add(newPath.toString()); return; } newPath.append("->"); if(root.left != null) dfs(root.left,newPath); if(root.right != null) dfs(root.right,newPath); } }
