首页 > 代码库 > [LeetCode]113 Binary Tree Postorder Traversal
[LeetCode]113 Binary Tree Postorder Traversal
https://oj.leetcode.com/problems/path-sum-ii/
http://fisherlei.blogspot.com/search?q=Path+Sum+II+
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
// 需要遍历树
// 对于每个节点，记录从root到此节点（包含）的路径值和路径，可以用map来储存
// 当遇到leaf，且符合条件，加入到result
List<List<Integer>> result = new ArrayList<>();
if (root == null)
return result;
Map<TreeNode, Path> pathmap = new HashMap<>();
pathmap.put(root, Path.append(new Path(), root));
find(root, sum, pathmap, result);
return result;
}
private void find(TreeNode node, int target, Map<TreeNode, Path> pathmap, List<List<Integer>> result)
{
Path path = pathmap.get(node);
if (node.left == null && node.right == null)
{
// A leaf
if (path.sum == target)
{
result.add(path.path);
}
return;
}
if (node.left != null)
{
Path leftpath = Path.append(path, node.left);
pathmap.put(node.left, leftpath);
find(node.left, target, pathmap, result);
}
if (node.right != null)
{
Path rightpath = Path.append(path, node.right);
pathmap.put(node.right, rightpath);
find(node.right, target, pathmap, result);
}
}
private static class Path
{
int sum;
List<Integer> path;
Path()
{
sum = 0;
path = new ArrayList();
}
static Path append(Path p, TreeNode node)
{
Path toReturn = new Path();
toReturn.sum = p.sum + node.val;
toReturn.path = new ArrayList<Integer>(p.path);
toReturn.path.add(node.val);
return toReturn;
}
}
}[LeetCode]113 Binary Tree Postorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。