路徑總和
給你二叉樹的根節(jié)點(diǎn) root 和一個(gè)表示目標(biāo)和的整數(shù) targetSum 。判斷該樹中是否存在 根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和 targetSum 。如果存在，返回 true ；否則，返回 false 玩祟。
葉子節(jié)點(diǎn) 是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。
遞歸
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return targetSum == root.val;
}
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}
沒有寫成以下是因?yàn)樽ぷ唬鏄錇榭招枰祷豧alse
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return targetSum == 0;
}
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}
迭代
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> sumQueue = new LinkedList<>();
queue.add(root);
sumQueue.add(root.val);
while (!queue.isEmpty()) {
root = queue.poll();
int sum = sumQueue.poll();
if (root.left == null && root.right == null) {
if (sum == targetSum) {
return true;
}
} else {
if (root.left != null) {
queue.add(root.left);
sumQueue.add(sum + root.left.val);
}
if (root.right != null) {
queue.add(root.right);
sumQueue.add(sum + root.right.val);
}
}
}
return false;
}
路徑總和 II
給你二叉樹的根節(jié)點(diǎn) root 和一個(gè)整數(shù)目標(biāo)和 targetSum 卵凑，找出所有 從根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 路徑總和等于給定目標(biāo)和的路徑。
葉子節(jié)點(diǎn) 是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)胜臊。
示例:
給定如下二叉樹勺卢，以及目標(biāo)和
sum = 22，5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1返回:
[
[5,4,11,2],
[5,8,4,5]
]
遞歸
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> ans = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
trace(root, sum, 0, ans, stack);
return ans;
}
public void trace(TreeNode root, int sum, int partSum, List<List<Integer>> lists, Stack<Integer> stack) {
if (root == null) {
return;
}
partSum += root.val;
stack.push(root.val);
if (root.left == null && root.right == null) {
if (partSum == sum) {
lists.add(new ArrayList<>(stack));
}
}
trace(root.left, sum, partSum, lists, stack);
trace(root.right, sum, partSum, lists, stack);
partSum -= root.val;
stack.pop();
}
迭代
public List<List<Integer>> pathSum(TreeNode root, int target) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
Queue<List<Integer>> pathQueue = new LinkedList<>();
queue.add(root);
pathQueue.add(new ArrayList<>(Arrays.asList(root.val, root.val)));
while (!queue.isEmpty()) {
root = queue.poll();
List<Integer> pathList = pathQueue.poll();
if (root.left == null && root.right == null) {
if (pathList.get(0) == target) {
pathList.remove(0);
res.add(pathList);
}
} else {
if (root.left != null) {
queue.add(root.left);
List<Integer> newPaths = new ArrayList<>(pathList);
newPaths.set(0, pathList.get(0) + root.left.val);
newPaths.add(root.left.val);
pathQueue.add(newPaths);
}
if (root.right != null) {
queue.add(root.right);
List<Integer> newPaths = new ArrayList<>(pathList);
newPaths.set(0, pathList.get(0) + root.right.val);
newPaths.add(root.right.val);
pathQueue.add(newPaths);
}
}
}
return res;
}
路徑總和 III
給定一個(gè)二叉樹象对，它的每個(gè)結(jié)點(diǎn)都存放著一個(gè)整數(shù)值黑忱。
找出路徑和等于給定數(shù)值的路徑總數(shù)。
路徑不需要從根節(jié)點(diǎn)開始勒魔，也不需要在葉子節(jié)點(diǎn)結(jié)束甫煞，但是路徑方向必須是向下的（只能從父節(jié)點(diǎn)到子節(jié)點(diǎn)）。
二叉樹不超過1000個(gè)節(jié)點(diǎn)冠绢，且節(jié)點(diǎn)數(shù)值范圍是 [-1000000,1000000] 的整數(shù)抚吠。
示例：
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
方法一：兩個(gè)DFS
先序遍歷每一個(gè)結(jié)點(diǎn)弟胀，以每一個(gè)結(jié)點(diǎn)作為根尋找滿足和的路徑
private int count;
public int pathSum(TreeNode root, int sum) {
preOrder(root, sum);
return count;
}
public void preOrder(TreeNode root, int sum) {
if (root == null) {
return;
}
trace(root, sum, 0);
preOrder(root.left, sum);
preOrder(root.right, sum);
}
private void trace(TreeNode root, int sum, int partSum) {
if (root == null) {
return;
}
partSum += root.val;
if (partSum == sum) {
count++;
}
trace(root.left, sum, partSum);
trace(root.right, sum, partSum);
}
方法二：前綴和
如果前綴總和currSum楷力，在節(jié)點(diǎn)A和節(jié)點(diǎn)B處相差target喊式，則位于節(jié)點(diǎn)A和節(jié)點(diǎn)B之間的元素之和是target
private Map<Integer, Integer> map = new HashMap<>();//key:前綴和 value：次數(shù)
public int pathSum(TreeNode root, int sum) {
map.put(0, 1);
return trace(root, sum, 0);
}
private int trace(TreeNode root, int sum, int partSum) {
if (root == null) {
return 0;
}
partSum += root.val;
int ans = 0;
ans += map.getOrDefault(partSum - sum, 0);
map.put(partSum, map.getOrDefault(partSum, 0) + 1);
ans += trace(root.left, sum, partSum);
ans += trace(root.right, sum, partSum);
//回到本層，恢復(fù)狀態(tài)萧朝，不再是前綴了
map.put(partSum, map.get(partSum) - 1);
return ans;
}
二叉樹中的最大路徑和
給定一個(gè)非空二叉樹岔留，返回其最大路徑和。
本題中检柬，路徑被定義為一條從樹中任意節(jié)點(diǎn)出發(fā)献联，達(dá)到任意節(jié)點(diǎn)的序列。該路徑至少包含一個(gè)節(jié)點(diǎn)何址，且不一定經(jīng)過根節(jié)點(diǎn)里逆。
示例 1:
輸入: [1,2,3]
1
/ \
2 3
輸出: 6
示例 2:
輸入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
輸出: 42
每走到一個(gè)結(jié)點(diǎn)，有三個(gè)選擇：
- 不走了
- 向左走
- 向右走
private int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
dfs(root);
return max;
}
public int dfs (TreeNode root) {
if (root == null) {
return 0;
}
int left = Math.max(0, dfs(root.left));//為負(fù)數(shù)就不向下走了
int right = Math.max(0, dfs(root.right));
max = Math.max(max, left + right + root.val);
return root.val + Math.max(left, right);//以root為根直路的長(zhǎng)度
}
二叉樹的所有路徑
給你一個(gè)二叉樹的根節(jié)點(diǎn) root 头朱，按 任意順序 运悲，返回所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑龄减。
葉子節(jié)點(diǎn) 是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)项钮。
示例 1：
輸入：root = [1,2,3,null,5]
輸出：["1->2->5","1->3"]
遞歸
private List<String> res = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
dfs(root, new Stack<>());
return res;
}
private void dfs(TreeNode root, Stack<Integer> stack) {
if (root == null) {
return;
}
stack.add(root.val);
if (root.left == null && root.right == null) {
StringBuilder sb = new StringBuilder();
for (int v : stack) {
sb.append(v).append("->");
}
sb.delete(sb.length() - 2, sb.length());
res.add(sb.toString());
}
dfs(root.left, stack);
dfs(root.right, stack);
stack.pop();
}
迭代
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
Queue<String> pathQueue = new LinkedList<>();
queue.add(root);
pathQueue.add(String.valueOf(root.val));
while (!queue.isEmpty()) {
root = queue.poll();
String s = pathQueue.poll();
if (root.left == null && root.right == null) {
res.add(s);
} else {
if (root.left != null) {
queue.add(root.left);
pathQueue.add(s + "->" + root.left.val);
}
if (root.right != null) {
queue.add(root.right);
pathQueue.add(s + "->" + root.right.val);
}
}
}
return res;
}
