深度优先遍历（DFS，全称为Depth First Traversal），是我们树或者图这样的数据结构中常⽤的⼀种遍历算法。这个算法会尽可能深的搜索树或者图的分⽀，直到⼀条路径上的所有节点都被遍历完毕，然后再回溯到上⼀层，继续找⼀条路遍历。
在⼆叉树中，常⻅的深度优先遍历为：前序遍历、中序遍历以及后序遍历。
因为树的定义本⾝就是递归定义，因此采⽤递归的⽅法去实现树的三种遍历不仅容易理解⽽且代码很
简洁。并且前中后序三种遍历的唯⼀区别就是访问根节点的时机不同，在做题的时候，选择⼀个适当的遍历顺序，对于算法的理解是⾮常有帮助的。

1. 计算布尔二叉树的值

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

算法思路：
这道题需要采用DFS，先访问左边的叶子节点，再访问右边的叶子节点，最后再访问根节点，因此可以采用后序遍历

算法流程：

1. 根据子问题设计出函数头：只需要一个参数root即可，返回值为boolean类型
2. 只关心某一个子问题，设计函数体：首先得到左边叶子的值，再得到右边叶子的值，再根据跟节点的值，将左右叶子的值进行操作
3. 递归的出口：当访问到叶子节点时，返回该叶子节点的值

实现代码：

class Solution {public boolean evaluateTree(TreeNode root) {if(root.left == null && root.right == 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. 求根节点到叶节点数字之和

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

解题思路：

1. 将父亲节点的值与当前节点的值整合起来向下传递，再将传递下来的值与下一个节点的值整合，并向下传递，直到遇到叶子节点时，将其与根节点的值整合后返回
2. 每个非叶子节点将左子树和右子树返回的值相加，并返回

递归函数设计：

1. 函数头：需要包含一个根节点参数，一个前序和参数，返回值为int
2. 函数体：更新前序和，向下传递，直至遇到叶子节点返回更新后的前序和，非叶子节点将左右返回的前序和相加并返回
3. 递归的出口：遇到叶子节点，返回前序和与叶子节点值的整合值

实现代码：

class Solution {public int sum;public int sumNumbers(TreeNode root) {return dfs(root, 0);}private int dfs(TreeNode root, int preSum) {preSum = 10 * preSum + root.val;if(root.left == null && root.right == null) return preSum;int ret = 0;if(root.left != null) ret += dfs(root.left, preSum);if(root.right != null) ret += dfs(root.right, preSum);return ret;}
}

3.二叉树剪枝

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

自己的解题思路：
从宏观上看，如果一个节点的左边可以移除，右边也可以移除，并且该节点的值为0，那么返回true给上一个节点，表明以该节点为根节点的树都可以移除。因此，该题需要采用后续遍历

实现代码：

class Solution {public TreeNode pruneTree(TreeNode root) {boolean rootTree = dfs(root);if(rootTree) return null;return root;}private boolean dfs(TreeNode root) {if(root == null) return true;boolean leftTree = dfs(root.left);if(leftTree) root.left = null;boolean rightTree = dfs(root.right);if(rightTree) root.right = null;return leftTree && rightTree && root.val == 0;}
}

答案解题思路：

1. 先处理掉左子树的剪枝，再处理右子树的剪枝，最后判断当前当前这棵树是否需要剪掉，因此需要采用后序遍历
2. 如果需要剪掉，那么父亲节点的左（或右）节点就需要置为NULL，即需要向上返回一个NULL；而当不需要剪掉时，为了保证递归解决问题的统一性，向上返回当前节点
3. 递归出口为当遍历到空节点时，向上返回NULL

实现代码：

class Solution {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.验证二叉搜索树

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

算法思路：
二叉搜索树的特点是：采用中序遍历得到的是一个严格递增的序列。因此，这道题采用中序遍历来解题。我们需要初始化一个无穷小（要比二叉搜索树里的最小值还要小，而题意-2³¹ <= Node.val <= 2³¹ - 1，比int类型的最小值还要小，可以用long类型的最小值）的全局变量prev用来记录root的前驱节点值，比较prev的值与当前节点的值，然后prev修改为当前节点的值

算法流程：

1. 定义一个全局变量，初始化为无穷小，用来记录前驱节点的值
2. 递归的出口：当root == null时，返回true
3. 先检查左子树是否是二叉搜索树，再判断当前节点是否满足二叉搜索树的性质（即前驱节点的值小于当前节点的值），再继续修改prev的值为当前节点的值，再去判断右子树是否是二叉搜索树
4. 只有当左子树为二叉搜索树，右子树为二叉搜索树，当前的节点也满足二叉搜索树的性质时，这棵树才是二叉搜索树

实现代码：

class Solution {public long prev = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root == null) return true;boolean leftTree = isValidBST(root.left);//剪枝if(!leftTree) return false;boolean cur = true;if(root.val <= prev) cur = false;//剪枝if(!cur) return false;prev = root.val;boolean rightTree = isValidBST(root.right);return leftTree && rightTree && cur;}
}

当左子树不是二叉搜索树，就表明已经这棵树不是二叉搜索树了，也就没有必要进行后续的操作了，直接向上返回false即可；同理，当当前节点不满足二叉搜索树的性质时，也直接向上返回false。剪枝操作是为了加快搜索过程

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

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

解题思路： 利用中序遍历，当访问到第k个“根节点”时，该节点对应的val值就是我们要找的第 K 小的元素

算法流程：

1. 递归的出口：当根节点为空时，返回-1，表明没有找到
2. 递归去左子树上去找，判断当前根节点是否是所需要找的节点（即判断k是否等于1），将k–，再递归去右子树上找

class Solution {public int K;public int kthSmallest(TreeNode root, int k) {K = k;return kthSmallest(root);}private int kthSmallest(TreeNode root) {if(root == null) return -1;int leftFind = kthSmallest(root.left, K);//剪枝if(leftFind != -1) return leftFind;if(K == 1) return root.val;K--;int rightFind = kthSmallest(root.right, K);return rightFind;}
}

注意： 这里需要定义一个全局变量K，而不是使用k作为递归的参数。因为当回溯时，k的值同样会回溯，这不符合算法的流程

6. 二叉树的所有路径

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

解题思路：

1. 除了根节点，其他节点前面都需要添加一个“->”
2. 需要一个字符串来添加路径，因此函数头需要一个字符串
3. 采用前序遍历，将根节点放入字符串中，再去遍历左子树、右子树
4. 当遍历到根节点时，将这时的字符串放入字符数组中
5. 递归的出口是：root == null

按照思路，我们能写出如下的代码

class Solution {private List<String> lists;public List<String> binaryTreePaths(TreeNode root) {lists = new LinkedList<String>();StringBuffer strBuff = new StringBuffer();dfs(root, strBuff);return lists;}private void dfs(TreeNode root, StringBuffer path) {if(root == null) return;if(!path.isEmpty()) path.append("->");path.append(root.val);if(root.left == null && root.right == null) {lists.add(path.toString());return;}dfs(root.left, path);dfs(root.right, path);}
}

实际上，这个代码是存在问题的！因为我们在递归完成后，没有对当前添加到 path的节点值进行删除操作，这就会导致在处理完这个路径后，后续的路径会附加在这个路径的字符串后面，从而导致最终的结果不正确

这是为什么呢？当函数返回时，path的值不是会回退到上一个函数的值吗？

答：当一个函数执行完毕返回时，函数内部的局部变量（比如基本数据类型的变量等）所占用的栈空间会被自动回收，其状态确实会 “撤销”，也就是这些局部变量会随着函数栈帧的销毁而消失。

例如，如果函数中有一个简单的 int 类型局部变量 count，每次进入函数它有不同的值，函数返回后，这个 count 变量所占用的内存空间会被释放，下次再进入该函数时，它可以重新被初始化并使用，从这个角度看是有自动 “撤销” 的过程。

递归确实会返回到上一个状态，但现在我们现在创建的字符串是一个对象，由于可变对象的状态管理不同于基本数据类型（如整数或字符），我们需要手动管理这种状态，以确保路径的正确记录

因此，我们需要在原代码的基础上，对字符串进行回溯（“恢复现场”）。另外，当我们解题时，如果使用了全局变量，也要去考虑该变量的回溯

修改后的代码：

class Solution {private List<String> lists;public List<String> binaryTreePaths(TreeNode root) {lists = new LinkedList<String>();StringBuffer strBuff = new StringBuffer();dfs(root, strBuff);return lists;}private void dfs(TreeNode root, StringBuffer path) {if(root == null) return;if(path.length() > 0) path.append("->");path.append(root.val);if(root.left == null && root.right == null) {lists.add(path.toString());} else {dfs(root.left, path);dfs(root.right, path);}//回溯int lastIndex = path.lastIndexOf(String.valueOf(root.val)) - 2;if(lastIndex >= 0) {path.delete(lastIndex, path.length());}}
}

另外，我们还可以通过创建一个局部变量——path的副本。在每次递归调用时，使用传入路径的副本。这允许每次递归都维护独立的路径，避免修改其他层级的路径。通过将 path 的内容复制到新的 StringBuffer _path 中，确保上下文保持准确，不会影响其他节点的路径。

代码如下：

class Solution {private List<String> lists;public List<String> binaryTreePaths(TreeNode root) {lists = new LinkedList<String>();StringBuffer strBuff = new StringBuffer();dfs(root, strBuff);return lists;}private void dfs(TreeNode root, StringBuffer path) {if(root == null) return;StringBuffer _path = new StringBuffer(path);if(_path.length() > 0) _path.append("->");_path.append(root.val);if(root.left == null && root.right == null) {lists.add(_path.toString());return;}dfs(root.left, _path);dfs(root.right, _path);}
}