LeetCode 113. Path Sum II DFS求解

113. Path Sum II

My SubmissionsQuestionTotal Accepted:72944Total Submissions:262389Difficulty:Medium

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree andsum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Subscribeto see which companies asked this question

Show Tags Show Similar Problems Have you met this question in a real interview? Yes No

給定一個目標數，找到一棵樹所有的根到葉子和為這個數的路徑。這道題比較簡單，普通的DFS深搜就可以解決。用一個list存儲路徑上的數。注意遞歸結束後把list的最後加入的數移除。

我的AC代碼

public class PathSumII {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		TreeNode n1 = new TreeNode(1);
		TreeNode n2 = new TreeNode(-2);
		TreeNode n3 = new TreeNode(-3);
		TreeNode n4 = new TreeNode(1);
		TreeNode n5 = new TreeNode(3);
		TreeNode n6 = new TreeNode(-2);
		TreeNode n7 = new TreeNode(-1);
		n1.left = n2;
		n1.right = n3;
		n2.left = n4;
		n2.right = n5;
		n3.left = n6;
		n4.left = n7;
		System.out.print(pathSum(n1, 2));
	}

	public static List> pathSum(TreeNode root, int sum) {
		List> result = new ArrayList>();
		if(root != null) dfs(root, sum, 0, new ArrayList(), result);
		return result;
    }
	
	private static void dfs(TreeNode root, int sum, int s, ArrayList path, List> result) {
		if(root.left == null && root.right == null) {
			if(s + root.val == sum) {
				path.add(root.val);
				result.add((List) path.clone());
				path.remove(path.size() - 1);
			}
			return;
		}
		
		path.add(root.val);
		if(root.left != null) dfs(root.left, sum, s + root.val, path, result);
		if(root.right != null) dfs(root.right, sum, s + root.val, path, result);
		path.remove(path.size() - 1);
	}
}