Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path's sum equals targetSum.

Question

Anonymous · Accepted Answer

public List> pathSum(TreeNode root, int targeSum) {
        return dfs(root, targeSum, new ArrayList());
    }

private List> dfs(TreeNode root, int targeSum, List list) {
        List> result = new ArrayList();

if(root==null) {
            return result;
        }
        
        if(root.left == null && root.right == null && targeSum - root.val == 0) {
            list.add(root.val);
            result.add(new ArrayList(list));
            list.remove(list.size()-1);
        }
        list.add(root.val);
        dfs(root.left, targeSum - root.val, list);
        dfs(root.right, targeSum - root.val, list);
        list.remove(list.size()-1);
        return result;
    }

No One · Answer

You're expected to answer 2 coding questions. That you only answered 1 means you failed.

neto · Answer

module ``Question`` =
    (*
    Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path's sum equals targetSum.
    *)
    
    type Tree =
        | Node of int*Tree*Tree
        | Leaf of int
    
    let answer initial target =
        
        let rec helper tree state =
            match tree with
            | Tree.Node (v, left, right) ->
                let state' = v :: state
                Seq.concat [helper left state'; helper right state']
            | Tree.Leaf v when Seq.sum state + v = target ->
                v :: state
                |> Seq.singleton
            | _ -> Seq.empty
            
        helper initial []
        |> Seq.map Seq.rev

JP · Answer

Or perhaps there were better candidates that did it faster.

Meta

Meta Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches

Work With Us