二叉树中的深搜

• 🎥 个人主页：Dikz12
• 🔥个人专栏：算法(Java)
• 📕格言：吾愚多不敏，而愿加学
• 欢迎大家👍点赞✍评论⭐收藏

目录

1. 计算布尔二叉树的值 

 1.1 题目描述

1.2 题解

1.3 代码实现 

 2. 求根节点到叶子节点数字之和

 2.1 题目描述

2.2 题解 

 2.3 代码实现

3. 二叉树剪枝

3.1 题目描述

3.2 题解 

3.3 代码实现 

4. 验证二叉搜索树 

4.1 题目描述 

 4.2 题解

4.3 代码实现 

 5.二叉搜索树中第k个小的元素

 5.1 题目描述

5.2 题解 

5.3 代码实现 

 6. 二叉树的所有路径

6.1 题目描述 

6.2 题解 

6.3 代码实现 

---

1. 计算布尔二叉树的值 

 1.1 题目描述

1.2 题解

递归函数设计：boolean evaluateTree(TreeNode root)

1. 返回值：当前节点值；
2. 参数：当前节点指针。
3. 函数作⽤：求得当前节点通过逻辑运算符得出的值。

递归函数流程：

1. 当前问题规模为 n=1 时，即叶⼦节点，直接返回当前节点值；
2. 递归求得左右⼦节点的值；
3. 通过判断当前节点的逻辑运算符，计算左右⼦节点值运算得出的结果；

1.3 代码实现 

    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. 求根节点到叶子节点数字之和

 2.1 题目描述

2.2 题解 

算法思路：

在前序遍历的过程中，我们可以往左右⼦树传递信息，并且在回溯时得到左右⼦树的返回值。递归函 数可以帮我们完成两件事：

1. 将⽗节点的数字与当前节点的信息整合到⼀起，计算出当前节点的数字，然后传递到下⼀层进⾏递 归；
2.  当遇到叶⼦节点的时候，就不再向下传递信息，⽽是将整合的结果向上⼀直回溯到根节点。 在递归结束时，根节点需要返回的值也就被更新为了整棵树的数字和。

 2.3 代码实现

    public int sumNumbers(TreeNode root) {return dfs(root,0);}public int dfs(TreeNode root,int preSum) {preSum = preSum * 10 + root.val;//递归出口if(root.left == null && root.right == null) {return preSum;}int num = 0;if(root.left != null) {num += dfs(root.left,preSum);}if(root.right != null) {num += dfs(root.right,preSum);}return num;}

3. 二叉树剪枝

3.1 题目描述

3.2 题解 

算法流程：

递归函数设计：void dfs(TreeNode root)

1. 返回值：⽆；
2. 参数 ：当前需要处理的节点；
3. 函数作⽤：判断当前节点是否需要删除，若需要删除，则删除当前节点。

后序遍历的主要流程：

1. 递归出⼝：当传⼊节点为空时，不做任何处理；
2. 递归处理左⼦树；
3. 递归处理右⼦树；
4. 处理当前节点：判断该节点是否为叶⼦节点（即左右⼦节点均被删除，当前节点成为叶⼦节点）， 并且节点的值为 0： a. 如果是，就删除掉； b. 如果不是，就不做任何处理。

3.3 代码实现 

    public TreeNode pruneTree(TreeNode root) {if(root == null) {return null;}root.left = pruneTree(root.left);root.right = pruneTree(root.right);if(root.left == null && root.right == null && root.val == 0) {root = null;}return root;}

4. 验证二叉搜索树 

4.1 题目描述 

 4.2 题解

算法思路：

如果⼀棵树是⼆叉搜索树，那么它的中序遍历的结果⼀定是⼀个严格递增的序列。

因此，我们可以初始化⼀个⽆穷⼩的全区变量，⽤来记录中序遍历过程中的前驱结点。那么就可以在 中序遍历的过程中，先判断是否和前驱结点构成递增序列，然后修改前驱结点为当前结点，传⼊下⼀ 层的递归中。

4.3 代码实现 

    long prev = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root == null) {return true;}boolean left = isValidBST(root.left);//剪枝if(left == false) {return false;}//当前节点boolean ret = false;if(prev < root.val) {prev = root.val;ret = true;    }boolean right = isValidBST(root.right);return left && ret && right;}

 5.二叉搜索树中第k个小的元素

 5.1 题目描述

5.2 题解 

算法思路：

上述解法不仅使⽤⼤量额外空间存储数据，并且会将所有的结点都遍历⼀遍。

但是，我们可以根据中序遍历的过程，只需扫描前 k 个结点即可。

因此，我们可以创建⼀个全局的计数器 count，将其初始化为 k，每遍历⼀个节点就将 count--。直到 某次递归的时候，count 的值等于 0，说明此时的结点就是我们要找的结果。

5.3 代码实现 

    int count;int ret;public int kthSmallest(TreeNode root, int k) {count = k;dfs(root);return ret;}public void dfs(TreeNode root) {if(root == null) {return;}dfs(root.left);count--;if(count == 0) {ret = root.val;return;}dfs(root.right);}

 6. 二叉树的所有路径

6.1 题目描述 

6.2 题解 

算法思路：

使⽤深度优先遍历（DFS）求解。

路径以字符串形式存储，从根节点开始遍历，每次遍历时将当前节点的值加⼊到路径中，如果该节点 为叶⼦节点，将路径存储到结果中。否则，将 "->" 加⼊到路径中并递归遍历该节点的左右⼦树。 定义⼀个结果数组，进⾏递归。递归具体实现⽅法如下：

1. 如果当前节点不为空，就将当前节点的值加⼊路径 path 中，否则直接返回；
2. 判断当前节点是否为叶⼦节点，如果是，则将当前路径加⼊到所有路径的存储数组 ret 中；
3. 否则，将当前节点值加上 "->" 作为路径的分隔符，继续递归遍历当前节点的左右⼦节点。
4. 返回结果数组。

6.3 代码实现 

    List<String> ret;public List<String> binaryTreePaths(TreeNode root) {ret = new ArrayList<>();dfs(root, new StringBuffer());return ret;}public void dfs(TreeNode root, StringBuffer _path) {StringBuffer path = new StringBuffer(_path);path.append(Integer.toString(root.val));if (root.left == null && root.right == null) {ret.add(path.toString());return;}path.append("->");if (root.left != null) {dfs(root.left, path);}if (root.right != null)dfs(root.right, path);}