首页 > 其他 > 详细

LintCode : Binary Tree Path Sum

时间:2016-04-17 21:58:08      阅读:96      评论:0      收藏:0      [点我收藏+]

Description:

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]
]
技术分享
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    private List<List<Integer>> result = new ArrayList<>();
    private ArrayList<Integer> path = new ArrayList<Integer>();
    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        // Write your code here
        // handel corner cases
        if (root == null) {
            return result;
        }
        path.add(root.val);
        helper(root, path, target - root.val);
        return result;
    }
    
    private void helper(TreeNode node, ArrayList<Integer> path, int target) {
        if (node.left == null && node.right == null) {
            if (target == 0) {
                result.add(new ArrayList<Integer>(path));
            }
            return;
        }
        if (node.left != null) {
            path.add(node.left.val);
            helper(node.left, path, target - node.left.val);
            path.remove(path.size() - 1);
        }
        if (node.right != null) {
            path.add(node.right.val);
            helper(node.right, path, target - node.right.val);
            path.remove(path.size() - 1);
        }
    }
}
View Code

Use the divide and conquer method, the most important thing here is to remove the last value after you have go deep to root.left or root.right, and also remember that if node.left == null and node.right == null, then it‘s time to return.

LintCode : Binary Tree Path Sum

原文:http://www.cnblogs.com/dingjunnan/p/5402299.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!