BrinaryTreePathSumToTarget 原

Binary Tree的一个基本题。

LeetCode: Path Sum II

```

/*

Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target.

A valid path is from root node to any of the leaf nodes.

Example

Given a binary tree, and target = 5:

1

/ \

2 4

/ \

2 3

return

[

[1, 2, 2],

[1, 4]

]

Tags Expand

Binary Tree Binary Tree Traversal

*/

/*

Thoughts:

path: has to be from root to leaf.

binary tree: no order logic in the tree.

DPS on all nodes. If final sum == target, add list of nodes into rst

*/

public class Solution {

public class TreeNode {

public int val;

public TreeNode left, right;

public TreeNode(int val) {

this.val = val;

this.left = this.right = null;

}

}

/**

* @param root the root of binary tree

* @param target an integer

* @return all valid paths

*/

public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {

List<List<Integer>> rst = new ArrayList<List<Integer>>();

if (root == null) {

return rst;

}

dfs(rst, new ArrayList<Integer>(), root, 0, target);

return rst;

}

private void dfs(List<List<Integer>> rst, ArrayList<Integer> list, TreeNode root, int add, int sum) {

if (root.left == null && root.right == null) {

if (add + root.val == sum) {

}

return;

}

if (root.left != null) {

dfs(rst, list, root.left, add + root.val, sum);

list.remove(list.size() - 1);

}

if (root.right != null) {

dfs(rst, list, root.right, add + root.val, sum);

list.remove(list.size() - 1);

}

}

}

暂无文章

shzwork

6
0
object 类中有哪些方法？

getClass(): 获取运行时类的对象 equals()：判断其他对象是否与此对象相等 hashcode()：返回该对象的哈希码值 toString()：返回该对象的字符串表示 clone()： 创建并返此对象的一个副本 wait...

happywe

6
0
Docker容器实战(七) - 容器中进程视野下的文件系统

JavaEdge

8
0

7
0

MtrS

5
0