pathSum 1
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
if (root.left == null && root.right == null && sum - root.val == 0) return true;
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
// comment:
// subtract/deduct each node.val from the target sum,
// UNTIL: if (root.left == null && root.right == null && sum - root.val == 0) return true;
//OTHERWISE: keep recursion and go deeper: return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
// First tentative idea:
// first sum all path, and store in an array
// then check their sum
}
}
pathSum 2
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
List<List<Integer>> resultList
這道二叉樹路徑之和在之前的基礎(chǔ)上又需要找出路徑 (可以參見我之前的博客 http://www.cnblogs.com/grandyang/p/4036961.html)慧耍，但是基本思想都一樣未辆，還是需要用深度優(yōu)先搜索DFS，只不過數(shù)據(jù)結(jié)構(gòu)相對復(fù)雜一點断箫，需要用到二維的vector瓜浸，而且每當(dāng)DFS搜索到新節(jié)點時澳淑，都要保存該節(jié)點。而且每當(dāng)找出一條路徑之后插佛，都將這個保存為一維vector的路徑保存到最終結(jié)果二位vector中杠巡。List<List<Integer>> resultList
并且，每當(dāng)DFS搜索到子節(jié)點雇寇，發(fā)現(xiàn)不是路徑和時氢拥，返回上一個結(jié)點時，需要把該節(jié)點從一維vector中移除锨侯。(轉(zhuǎn)載出處)
class Solution {
private List<List<Integer>> resultList = new ArrayList<List<Integer>>();
// A list of List<Integer>
// List<List<Integer>> resultList
public void pathSumInner(TreeNode root, int sum, Stack<Integer>path){
path.push(root.val);
if(root.left == null && root.right == null) {
if (sum == root.val) resultList.add(new ArrayList<Integer>(path));
// 只有最終符合條件的才會加入resultList
}
if(root.left != null) {
pathSumInner(root.left, sum - root.val, path);
}
if(root.right != null) {
pathSumInner(root.right, sum - root.val, path);
}
path.pop(); // 不符合條件的node嫩海，pop出Stack<Integer>(path)
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if (root == null) {return resultList;}
Stack<Integer> path = new Stack<Integer>();
pathSumInner(root, sum, path);
return resultList;
}
}
pathSum 3
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
