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
    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:

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

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

    this should return 3, your code would return 1.

    broken path

    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.