转换升序数组为二叉搜索树(108)
因为数组是有序的，我们可以使用二分的思路，每次取mid为根，再将剩余的数据分列在左右两侧，因为二分可能会导致左右两边的个数不均衡，相差1，正好满足二叉搜索树两侧的树高度相差不超过一的限制。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public TreeNode sortedArrayToBST(int[] num) {
if (num == null || num.length == 0) return null;
return helper(num, 0, num.length - 1);
}
/**
* Recursive, DFS
* Divide into left subtree and right subtree with indices range
* Choose mid point as the root of subtree
*/
public static TreeNode helper(int[] num, int left, int right) {
if (left > right) return null;
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(num[mid]);
root.left = helper(num, left, mid - 1); // left and mid -1
root.right = helper(num, mid + 1, right); // mid + 1 and right
return root;
}
路径之和(112)
判断一个树从树根到树叶的和是否有一条为sum，这道题和求树高的题相反，不需要先知道叶子节点的数据再依次计算上层的数据，而是 一开始就知道了结果，正向向下去验证是否有这样一条path，如果有即返回。当然还是要用递归，但是因为递归就意味着每层都会多出分叉 的逻辑，所以只要有一个分支满足即返回，所以每一层的逻辑之间是或的关系，而每一层的sum都是上一层的sum减去上一层节点的值的结果。
1
2
3
4
5
6
7
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false; // root == null
sum -= root.val; // update sum
// leaf? sum == 0? left subtree? right subtree?
return root.left == null && root.right == null && sum == 0
|| hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
路径之和2(113)
每一轮将当前轮的值从目标和中减掉，并将当前节点加入到当前计算的路径中，然后一直向叶子节点方向计算，如果到达叶子节点，且sum为0，则找到了一条路径。
注意：为了避免深度搜索中出栈后对集合引用的操作会影响以保存的结果，需要每次都拷贝一份存储。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
dfs(root, sum, new ArrayList<>(), res);
return res;
}
public void dfs(TreeNode root, int sum, List<Integer> path, List<List<Integer>> res) {
if (root == null) return;
// 每一层处理时先将本层数据减去
sum -= root.val;
if (root.left == null && root.right == null && sum == 0) {
path.add(root.val);
res.add(new ArrayList<>(path)); // 重新实例化一份新的数据
path.remove(path.size() - 1); // 将当前层的数据从path中减掉，以便回到上一层后仍然是之前的结构
return;
}
// 未到达叶子节点，把当前节点的值加入到路径中
path.add(root.val);
dfs(root.left, sum, path, res);
dfs(root.right, sum, path, res);
path.remove(path.size() - 1);
}
二叉树的高度最小值(111)
即从根节点到某一个叶子节点的路径值最小和104题的计算逻辑相反
1
2
3
4
5
6
7
8
9
10
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = minDepth(root.left);
int right = minDepth(root.right);
if (left == 0) return right + 1;
if (right == 0) return left + 1;
return Math.min(left, right) + 1; // plus root
}
二叉树最大深度(104)
二叉树的深度为左子树或右子数的深度的最大值，采用递归的方式，计算子树的高度后再加1就是本层的高度。
1
2
3
4
5
6
7
8
private int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
References
- https://leetcode.com
本文首次发布于 LiuShuo’s Blog, 转载请保留原文链接.
