【Java算法】二叉树的深搜

  🔥个人主页： 中草药 

 🔥专栏：【算法工作坊】算法实战揭秘

---

一.2331.计算布尔二叉树的值

题目链接：2331.计算布尔二叉树的值

代码

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;}

算法原理 

是一个相对简单的递归二叉树深搜的问题，注意分析 return 的内容

这个算法基于递归树遍历和布尔表达式求值的原理。具体来说：

• 递归树遍历：从根节点开始，递归地访问每个节点，直到到达叶子节点。在回溯过程中，将叶子节点的值逐步向上层传递，并根据父节点的逻辑运算符进行组合。
• 布尔表达式求值：通过递归的方式，最终可以将整个二叉树转换成一个布尔表达式，并计算出最终的结果。在这个过程中，每遇到一个内部节点（即值为 2 或 3 的节点），就相当于在布尔表达式中遇到了一个逻辑运算符，然后根据这个运算符对左右子树的结果进行相应的逻辑运算。

假设我们有以下二叉树：

    2/ \1   3/ \0   1

• 根节点的值为 2，表示 OR 运算。
• 左子树的根节点值为 1，直接返回 true。
• 右子树的根节点值为 3，表示 AND 运算。
  • 右子树的左子节点值为 0，直接返回 false。
  • 右子树的右子节点值为 1，直接返回 true。
  • 右子树的 AND 结果为 false && true，即 false。
• 最终结果为 true || false，即 true。

因此，对于上面的二叉树，evaluateTree 函数会返回 true

二.求根节点到叶结点数字之和

题目链接：求根节点到叶结点数字之和

代码

public int sumNumbers(TreeNode root) {if(root==null){return -1;}return dfs(root,0);}public int dfs(TreeNode root,int preSum){//1.实现数字的计算preSum=preSum*10+root.val;//2.函数的出口if(root.left==null&&root.right==null){return preSum;}int ret=0;//3.计算所有的左支路if(root.left!=null){ret+=dfs(root.left,preSum);}//计算所有的右支路if(root.right!=null){ret+=dfs(root.right,preSum);}return ret;}

算法原理 

创建一个数 preNum 用于记录之前的数，可以用 preSum*10+root.val 来实现数字的计算，来实现题目要求

1. 深度优先搜索 (DFS)：这个算法使用了深度优先搜索的方法来遍历二叉树。每次递归调用时，都会沿着一个分支深入下去，直到到达叶子节点。
2. 前缀和累积：在每次递归调用中，通过将当前节点的值乘以10并加上之前的前缀和，逐步构建从根节点到当前节点的数字。
3. 路径和累加：当到达叶子节点时，返回当前路径形成的数字。对于非叶子节点，递归地计算其左子树和右子树的路径和，并将这些路径和累加起来。

三.814.二叉树剪枝

题目链接：814.二叉树剪枝

代码

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){return null;}return root;}

算法原理 

 这道题，可以看做剪枝思路的一个引入，注意函数体中 if 里面的条件实现剪枝，一步步剪枝

1. 递归遍历：算法使用了深度优先搜索（DFS）的方式递归遍历整棵树。从根节点开始，逐步向下遍历到叶子节点，然后再回溯上来。
2. 自底向上修剪：在递归过程中，先处理子节点，再处理父节点。这样可以在处理父节点时，已经知道子节点的状态（是否被移除）。
3. 条件判断：对于每个节点，检查其左右子节点是否已经被移除（即 root.left == null 和 root.right == null），并且当前节点的值是否为 0。如果满足这些条件，说明当前节点是一个值为 0 的叶子节点，应该被移除。
4. 更新引用：通过将 root.left 和 root.right 设置为递归调用的结果，来更新当前节点的子节点引用。如果子节点被移除，则相应的子节点引用会被设置为 null。

详细步骤

1. 基本情况：如果当前节点为空，直接返回 null。
2. 递归修剪：递归调用 pruneTree 处理当前节点的左子树和右子树。
3. 检查当前节点：如果当前节点是值为 0 的叶子节点（即左右子节点都为 null 且当前节点的值为 0），则返回 null 以移除该节点。
4. 返回结果：否则，返回当前节点，表示当前节点及其子树不需要被移除

 四.98.验证二叉搜索树

题目链接：98.验证二叉搜索树

代码

//防止出现极端数据long prev=Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}boolean left = isValidBST(root.left);boolean cur = false;if (root.val > prev) {prev = root.val;cur = true;}boolean right = isValidBST(root.right);return left && right && cur;}

算法原理

二叉搜索树的一个关键特征--中序遍历一定是升序的，正确引用全局变量可以节省函数头的设计，初始设置 cur 节点为 fasle ，符合要求才将该节点设置为 true，根据题意来设置 return 

1. 中序遍历：这个算法利用了二叉搜索树的一个重要特性，即中序遍历（左-根-右）的结果是一个严格递增的序列。因此，通过中序遍历的方式，可以逐个检查节点的值是否满足递增的条件。
2. 递归遍历：算法使用递归的方法进行中序遍历。先递归处理左子树，然后处理当前节点，最后递归处理右子树。
3. 全局变量 prev：使用一个全局变量 prev 来记录上一个访问的节点的值。每次访问一个新的节点时，都检查当前节点的值是否大于 prev。如果是，则更新 prev 为当前节点的值。
4. 有效性检查：如果在某个节点处发现当前节点的值不大于 prev，则说明该树不是有效的二叉搜索树，返回 false。否则，继续递归检查其他节点。

详细步骤

1. 基本情况：如果当前节点为空，直接返回 true。
2. 递归检查左子树：递归调用 isValidBST 处理当前节点的左子树。
3. 检查当前节点：
   • 检查当前节点的值是否大于 prev。如果是，则更新 prev 为当前节点的值，并将 cur 设置为 true。
   • 如果当前节点的值不大于 prev，则将 cur 设置为 false，表示该树不是有效的BST。
4. 递归检查右子树：递归调用 isValidBST 处理当前节点的右子树。
5. 返回结果：返回左子树、右子树和当前节点的检查结果的逻辑与操作。

 五.230.二叉搜索树中第k小的元素

题目链接：230.二叉搜索树中第k小的元素

代码

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||count==0){return;}//中序遍历dfs(root.left);count--;if(count==0){ret=root.val;}//剪枝if(count==0){return;}dfs(root.right);}

算法原理 

由于中序遍历一定是升序的我们只需让一个 count 为k值，每遍历一次 count-- ，即可，我们还可以通过 剪枝 的方式优化代码

1. 中序遍历：利用二叉搜索树的特性，中序遍历可以生成一个递增的序列。因此，通过中序遍历，我们可以按顺序访问所有节点。
2. 计数器 count：使用全局变量 count 来记录还需要访问多少个节点才能到达第 k 个最小的节点。每次访问一个节点时，count 减 1。
3. 找到目标节点：当 count 变为 0 时，说明当前节点就是第 k 个最小的节点，将其值存储在 ret 中。
4. 剪枝优化：一旦找到第 k 个最小的节点，就不需要继续遍历剩余的节点了。通过检查 count 是否为 0，可以在找到目标节点后立即返回，从而减少不必要的计算。

详细步骤

1. 初始化：在 kthSmallest 方法中，初始化 count 为 k。
2. 中序遍历：调用 dfs 方法开始中序遍历。
   • 递归地访问左子树。
   • 访问当前节点，将 count 减 1。
   • 如果 count 变为 0，更新 ret 为当前节点的值。
   • 如果 count 为 0，直接返回，不再访问右子树。
   • 否则，继续递归地访问右子树。
3. 返回结果：在 kthSmallest 方法中返回 ret。

六.257.二叉树的所有路径*

题目链接：257.二叉树的所有路径*

代码

 public List<String> binaryTreePaths(TreeNode root) {retl=new ArrayList<>();dfs(root,new StringBuilder());return retl;}public void dfs(TreeNode root,StringBuilder _path){//每次设置为新的，实现了回溯的时候 回到那时候的path//回溯StringBuilder path=new StringBuilder(_path);path.append(Integer.toString(root.val));if(root.left==null&&root.right==null){retl.add(path.toString());return;}path.append("->");//剪枝if(root.left!=null){dfs(root.left,path);}if(root.right!=null){dfs(root.right,path);}}

算法原理

在这道题初步运用了回溯的思想，并且用剪枝优化了函数的出口，需要仔细理解反复揣摩

1. 深度优先搜索 (DFS)：算法使用了深度优先搜索的方法来遍历整棵树。从根节点开始，逐步深入到叶子节点。
2. 路径构建：使用 StringBuilder 来构建从根节点到当前节点的路径。每次访问一个节点时，将该节点的值添加到路径中。
3. 回溯：通过在每次递归调用时创建一个新的 StringBuilder 对象 path，确保每次递归调用时路径都是独立的。这样在回溯时，路径可以恢复到之前的正确状态。
4. 路径存储：当到达叶子节点时，将当前路径转换为字符串并添加到结果列表 retl 中。
5. 剪枝优化：如果某个子树为空，则不需要继续递归处理该子树，从而减少不必要的计算。

详细步骤

1. 初始化：在 binaryTreePaths 方法中，初始化 retl 为一个新的 ArrayList。
2. 递归遍历：调用 dfs 方法开始深度优先搜索。
   • 创建一个新的 StringBuilder 对象 path，并将其内容初始化为 _path 的内容。
   • 将当前节点的值添加到 path 中。
   • 如果当前节点是叶子节点，将 path 转换为字符串并添加到 retl 中。
   • 否则，在路径末尾添加 "->"。
   • 递归地处理左子树和右子树，分别传入当前路径 path。
3. 返回结果：在 binaryTreePaths 方法中返回 retl