2 lines Java


  • 0
    W
    public int pathSum(TreeNode node, int sum) {
        return pathSum(node, sum, true);
    }
    
    public int pathSum(TreeNode node, int sum, boolean isOriginal) {
        return null == node ? 0 : pathSum(node.left, sum - node.val, false) + pathSum(node.right, sum - node.val, false) + (node.val == sum ? 1 : 0) + (isOriginal ? pathSum(node.left, sum, true) + pathSum(node.right, sum, true) : 0);
    }

  • 0
    K

    Hi, my idea is similar but didn't use isOriginal, so it doesn't work, can you explain why we need isOriginal here? thanks


  • 0
    W

    @Kenigma

    You are welcome
    isOriginal is a flag represents whether we have use the current node already. I'm not sure whether it is a suitalbe name.

    For example,

            10
           /  \
          5   -3
         / \    \
        3   2   11
       / \    \
      3  -2    1
    

    Let we need find 8 paths. If you use node 10, then you will seach 10's children with sum 8-10 = -2. Cause you use 10 already , you can not make 5->3 a valid path.


  • 0
    K

    thanks, i actually figured out myself, it is used to prevent searching for a different sum starting other nodes other than root


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.