二叉树中和为某一值的路径

Posted on In Views: Waline: Views: Symbols count in article: 526 Reading time ≈ 1 mins.

题解方法

  • 深度优先搜索

深度优先搜索

  1. do 访问节点：
    1. If NULL，return。
    2. 添加当前节点。
    3. If 叶子节点，判断路径总和是否等于给定目标和的路径。
    4. 递归访问左右子节点。
    5. 移除当前节点。

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void search(TreeNode root, List<Integer> path) {
	if (root == null) {
		return;
	}

	path.add(root.val);

	if (root.left == null && root.right == null) {
		// List 求和
		int sum = path.stream().mapToInt(Integer::intValue).sum();
		if (sum == target) {
			paths.add(new ArrayList<>(path));
		}
	}
	search(root.left, path);
	search(root.right, path);

	path.remove(path.size() - 1);
}

题目来源

二叉树中和为某一值的路径 - 力扣（LeetCode）