本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
112. 路径总和
本题来自 LeetCode：112. 路径总和[1]
题目描述
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/
4 8
/ /
11 13 4
/
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5-4-11-2。
题目分析
本题采用深度优先遍历，计算每条从根节点到叶子节点的路径的和是否等于目标值。
题目解答
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null) {
return false;
}
sum -= root.val;
if(root.left == null && root.right == null) {
if(sum == 0) {
return true;
}
return false;
}
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
}
复杂度分析：
时间复杂度：
O(n)，每个节点访问一次
空间复杂度：
O(n)，调用栈最大为
n
113. 路径总和 II
本题来自 LeetCode：113. 路径总和 II[2]
题目描述
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/
4 8
/ /
11 13 4
/ /
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
题目分析
本题采用深度优先遍历，加回溯算法解答。
题目解答
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public ListListInteger pathSum(TreeNode root, int sum) {
ListListInteger paths = new LinkedList();
if(root == null) {
return paths;
}
dfs(root, sum, new LinkedList(), paths);
return paths;
}
public void dfs(TreeNode root, int remaining, ListInteger path, ListListInteger paths) {
remaining = remaining - root.val;
// 若为叶节点
if(root.left == null && root.right == null) {
// 路径总和等于目标值
if(remaining == 0) {
ListInteger newPath = new ArrayList(path);
newPath.add(root.val);
paths.add(newPath);
}
return;
}
path.add(root.val);
if(root.left != null) {
dfs(root.left, remaining, path, paths);
}
if(root.right != null) {
dfs(root.right, remaining, path, paths);
}
path.remove(path.size() - 1);
}
}
复杂度分析：
时间复杂度：
O(n)，每个节点访问一次
空间复杂度：
O(n)，调用栈最大为
n
437. 路径总和 III
本题来自 LeetCode：437. 路径总和 III[3]
题目描述
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过 1000 个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/
5 -3
/
3 2 11
/
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 - 3
2. 5 - 2 - 1
3. -3 - 11
题目分析
本题和
113. 路径总和 II的不同在于，不需要从根节点出发，可以从任意一个节点出发；也不需要在叶子节点结束，可以在任意一个子节点结束。
本题采用深度优先遍历，加回溯算法解答。
题目解答
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int count = 0;
public int pathSum(TreeNode root, int sum) {
if(root == null) {
return 0;
}
ListTreeNode queue = new LinkedList();
queue.add(root);
while(!queue.isEmpty()) {
TreeNode node = queue.remove(0);
// 以当前节点作为根节点（起始节点）
dfs(node, sum);
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
return count;
}
public void dfs(TreeNode root, int remaining) {
remaining -= root.val;
// 如果当前路径上的和等于目标值
if(remaining == 0) {
count ++;
}
// 继续计算左节点这条路径
if(root.left != null) {
dfs(root.left, remaining);
}
// 继续计算右节点这条路径
if(root.right != null) {
dfs(root.right, remaining);
}
}
}
复杂度分析：
时间复杂度：
O(n * n)，每个节点访问
n次
空间复杂度：
O(n)，调用栈最大为
n
参考资料
原文始发于微信公众号（xiaogan的技术博客）：
