C++ 5 Line Body Code DFS Solution


  • 30

    For tree structure problems. recursion is usually intuitive and easy to write. lol

    class Solution {
    public:
        int pathSum(TreeNode* root, int sum) {
            if(!root) return 0;
            return sumUp(root, 0, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
        }
    private:
        int sumUp(TreeNode* root, int pre, int& sum){
            if(!root) return 0;
            int current = pre + root->val;
            return (current == sum) + sumUp(root->left, current, sum) + sumUp(root->right, current, sum);
        }
    };
    

  • 0
    J

    can you explain a bit? ;)


  • 1

    @jeanmuu sumUp function recursively calculate the path sum start from root, compares every intermediate status with SUM. pathSum returns any possible routes start from current root, and recursively compute the subtrees. Hope it helps.


  • 5
    H

    Won't the complexity of this solution be O(N^2) ?

    Essentially, you start at root and find the number of root->anyNode solutions.
    And you recurse on root->left and root->right.

    Nice solution though!


  • 0
    K

    Very good ieda!


  • 0
    Q

    In function sumUp(), why "int& sum"?


  • 3
    S

    same idea with you:

    class Solution {
    public:
        int rootSum(TreeNode* root, int sum) {
            if (root == nullptr)
                return 0;
            return (sum == root->val) + rootSum(root->left, sum - root->val) + rootSum(root->right, sum - root->val);
        }
        
        int pathSum(TreeNode* root, int sum) {
            if (root == nullptr)
                return 0;
            return rootSum(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
        }
    }
    ``

  • 0

    elegant solution


  • 0
    S

    Could explain the meaning of this statement?
    " return (current == sum) + sumUp(root->left, current, sum) + sumUp(root->right, current, sum);"

    since "current==sum" is boolean while the return value of sumUp is "int", why you can sum them up?


  • 0

    @steven5 Because in c++, boolean 'true' is equivalent to int 1. Maybe you want to read this: http://stackoverflow.com/questions/5369770/bool-to-int-conversion


  • 0

    @humachine Thank you so much for suggestion!


  • 0
    P

    @Simpleyyt
    Much elegant solution.


  • 0
    C

    Does anyone know the difference between this code with other languages?

    func getNum(root: TreeNode?, sum: Int) -> Int {
        guard let r = root else { return 0 }
        return (sum == r.val) ? 1:0 + getNum(root: r.left, sum: sum - r.val) + getNum(root: r.right, sum: sum - r.val)
    }
    
    func pathSum(_ root: TreeNode?, _ sum: Int) -> Int {
        guard let r = root else { return 0 }
        return getNum(root: r, sum: sum) + pathSum(r.left, sum) + pathSum(r.right, sum)
    }
    

    When input is

    [1,-2,-3,1,3,-2,null,-1]
    -1
    

    LeetCode say it is Wrong Answer.


  • 0
    C

    @cpo007
    It is Swift Code, I don't know why error.


  • 0
    U

    Could you please tell me why my answer is wrong???
    int pathSum(TreeNode* root, int sum) {
    if(!root)return 0;
    return (sum==root->val)+pathSum(root->left,sum-root->val)+pathSum(root->left,sum)+pathSum(root->right,sum-root->val)+pathSum(root->right,sum);

    }

  • 1
    E

    @UncleLewis
    In your code the nodes you selected are not guaranteed to be consecutive.
    say 5->3->3, your answer could be 2 (you picked 5 and the first 3 once, and then 5 with the second 3 again)


  • 0
    U

    @eltiese thank you, I got your point now...


  • 0
    I

    @Undo nice solution


  • 0
    R

    @Undo nice solution!


  • 0
    T

    whats the complexity of this ? 0(N) ?


Log in to reply
 

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