首页 > 代码库 > leetcode--Path Sum

leetcode--Path Sum

2024-07-07 09:07:03   222人阅读

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.

For example:
Given the below binary tree and sum = 22,

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

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * This problem can be solved either by dfs or bfs.<br>
     * @param root
     * @param sum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int sum) {
        boolean exists = false;
        if(root != null){
            Map<TreeNode, Integer> sumAtNode = new HashMap<TreeNode, Integer>();
            sumAtNode.put(root, root.val);
            Deque<TreeNode> nodes = new LinkedList<TreeNode>();
            nodes.add(root);
            while(nodes.peek()!= null){
                TreeNode aNode = nodes.poll();
                if(aNode.left == null && aNode.right == null){
                    if(sumAtNode.get(aNode) == sum){
                        exists = true;
                        break;
                    }
                }
                else{
                    int pareValue = http://www.mamicode.com/sumAtNode.get(aNode);
                    if(aNode.left != null){
                        sumAtNode.put(aNode.left, aNode.left.val + pareValue);
                        nodes.add(aNode.left);
                    }
                    if(aNode.right != null){
                        sumAtNode.put(aNode.right, aNode.right.val + pareValue);
                        nodes.add(aNode.right);
                    }
                }
            }
        }
        return exists;  
    }
}

　　


联系
我们