Can anyone help? Java DFS solution but have some problem _(:з」∠)_


  • 0

    Re: Simple AC Java Solution DFS

    @star1993 hi, actually I have the same idea, but my solution can not figure out whether the subPath is linked together. for example, in the case
    [10,5,-3,3,2,null,11,3,-2,null,1]
    8
    it will return 4 rather than 3, since it count (10) -> (-2) as 1 answer

        public int pathSum(TreeNode root, int sum) {
            if (root == null) {return 0;}
            if (root.val == sum) {
            return 1;}
            else {
                return (pathSum(root.left, sum - root.val) + pathSum(root.right, sum - root.val) + pathSum(root.left, sum) + pathSum(root.right, sum));
            }
        }
    

    I tried to think of it pvernight but still confusing, can any one help me?


  • 0

    @monster-gump The way you implemented make it possible to have a broken path, so you have 10-2 = 8 as an answer.. You can check my solution.


  • 0

    sry, but since I used

    pathSum(root.left, sum) + pathSum(root.right, sum)
    

    I think it should start from root.left and root.right then, so what's wrong here?
    I consider the main problem is that I can't split the connection from the very beginning, which means the maybe some nodes I didn't use for the path, but I don't know how to get rid of them


  • 1

    @monster-gump Not sure what exactly do you mean... But here are some thoughts:

    first,
    this is not a valid base case, because we have nodes with negative value.

            if (root.val == sum) {
            return 1;}
    

    e.g.
    [0,1,null,-1]
    0
    this should return 3, your code would return 1.

    second,
    broken path

    e.g.
    [1,2,null,3]
    4
    this should return 0, your code would return 1.

    I'll use the node value to represent the node, and show the call stacks returns 1.
    call stack0: pathSum(root.left, sum) -> pathSum(1, 4)
    call stack1: pathSum(root.left, sum - root.val) -> pathSum(1.left, 4 - 1) -> pathSum(2, 3)
    call stack2: pathSum(root.left, sum) -> pathSum(2.left, 3) -> pathSum(3, 3)
    then returns 1.

    So you need a way to make sure that the path doesn't split in the middle.

    Hope it helps.


  • 0

    @crickey180 I see.
    when I review this question I notice my idea is totally wrong, I just wanted to wrap up everything in the main function but is seems impossible.
    your solution is also a smart one.
    Thx for explain it in detail.


  • 0

    @monster-gump You are welcome~


Log in to reply
 

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