Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5
All root-to-leaf paths are:

["1->2->5", "1->3"]

DFS

public List<String> binaryTreePaths(TreeNode root) {
    List<String> res = new ArrayList();

    if(root == null) return res;

    Helper(res, String.valueOf(root.val), root);

    return res;
}

public void Helper(List<String> res, String comb, TreeNode root) {
    if(root.left == null && root.right == null){
        res.add(comb);
    }else{
        if(root.left != null){
            Helper(res, comb + "->" + root.left.val, root.left);
        }
        if(root.right != null){
            Helper(res, comb + "->" + root.right.val, root.right);
        }
    }
}

BFS

public List<String> binaryTreePaths(TreeNode root) {
    List<String> res = new ArrayList();

    if(root == null) return res;

    Queue<TreeNode> que = new LinkedList();
    Queue<String> path = new LinkedList();

    que.add(root);
    path.add(String.valueOf(root.val));

    while(!que.isEmpty()){
        TreeNode n = que.poll();
        String currPath = path.poll();

        if(n.left == null && n.right == null){
            res.add(currPath);
        }

        if(n.left != null){
            que.add(n.left);
            path.add(currPath + "->" + n.left.val);
        }

        if(n.right != null){
            que.add(n.right);
            path.add(currPath + "->" + n.right.val);
        }
    }

    return res;
}

results matching ""

    No results matching ""