目录
1. 计算布尔二叉树的值
1.1 题目描述
1.2 题解
递归函数设计：boolean evaluateTree(TreeNode root)
- 返回值：当前节点值；
- 参数：当前节点指针。
- 函数作⽤：求得当前节点通过逻辑运算符得出的值。
递归函数流程：
- 当前问题规模为 n=1 时，即叶⼦节点，直接返回当前节点值；
- 递归求得左右⼦节点的值；
- 通过判断当前节点的逻辑运算符，计算左右⼦节点值运算得出的结果；
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 题解
算法思路：
在前序遍历的过程中，我们可以往左右⼦树传递信息，并且在回溯时得到左右⼦树的返回值。递归函 数可以帮我们完成两件事：
- 将⽗节点的数字与当前节点的信息整合到⼀起，计算出当前节点的数字，然后传递到下⼀层进⾏递 归；
- 当遇到叶⼦节点的时候，就不再向下传递信息，⽽是将整合的结果向上⼀直回溯到根节点。 在递归结束时，根节点需要返回的值也就被更新为了整棵树的数字和。
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)
- 返回值：⽆；
- 参数 ：当前需要处理的节点；
- 函数作⽤：判断当前节点是否需要删除，若需要删除，则删除当前节点。
后序遍历的主要流程：
- 递归出⼝：当传⼊节点为空时，不做任何处理；
- 递归处理左⼦树；
- 递归处理右⼦树；
- 处理当前节点：判断该节点是否为叶⼦节点（即左右⼦节点均被删除，当前节点成为叶⼦节点）， 并且节点的值为 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）求解。
路径以字符串形式存储，从根节点开始遍历，每次遍历时将当前节点的值加⼊到路径中，如果该节点 为叶⼦节点，将路径存储到结果中。否则，将 "->" 加⼊到路径中并递归遍历该节点的左右⼦树。 定义⼀个结果数组，进⾏递归。递归具体实现⽅法如下：
- 如果当前节点不为空，就将当前节点的值加⼊路径 path 中，否则直接返回；
- 判断当前节点是否为叶⼦节点，如果是，则将当前路径加⼊到所有路径的存储数组 ret 中；
- 否则，将当前节点值加上 "->" 作为路径的分隔符，继续递归遍历当前节点的左右⼦节点。
- 返回结果数组。
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);
}