Binary Tree Paths

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

Note: A leaf is a node with no children.

Example:

Input:  tree={1,2,3,null,5}
Output: [1->2->5,1->3]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BinaryTreePaths {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(5);
        List<String> paths = binaryTreePaths(root);
        System.out.println(Arrays.asList(paths));
    }

    static List<List<Integer>> res;

    static List<String> binaryTreePaths(TreeNode root) {
        res = new ArrayList<List<Integer>>();
        List<String> ans = new ArrayList<String>();
        dfs(root, new int[1000], 0);
        for (int i = 0; i < res.size(); i++) {
            StringBuffer str = new StringBuffer();
            for (int j = 0; j < res.get(i).size(); j++) {
                str.append(String.valueOf(res.get(i).get(j)));
                if (j != res.get(i).size() - 1)
                    str.append("->");
            }
            ans.add(str.toString());
        }
        return ans;
    }

    static void dfs(TreeNode root, int[] path, int len) {
        if (root == null)
            return;
        path[len++] = root.val;
        // If the node is leaf node
        if (root.left == null && root.right == null) {
            List<Integer> l = new ArrayList<Integer>();
            for (int i = 0; i < len; i++) {
                l.add(path[i]);
            }
            res.add(l);
            return;
        }
        // If the node is not a leaf node
        else {
            // call for left subtree
            dfs(root.left, path, len);

            // call for right subtree
            dfs(root.right, path, len);
        }
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode
{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
vector<vector<int>> res;
void dfs(TreeNode *root, vector<int> path)
{
    if (root == NULL)
        return;
    path.push_back(root->data);
    //If the node is leaf node
    if (root->left == NULL && root->right == NULL)
        res.push_back(path);
    //If the node is not a leaf node
    else
    {
        //call for left subtree
        dfs(root->left, path);

        //call for right subtree
        dfs(root->right, path);
    }
}
vector<string> binaryTreePaths(TreeNode *root)
{
    res.clear();
    vector<int> path;
    vector<string> ans;
    dfs(root, path);
    for (int i = 0; i < res.size(); i++)
    {
        string str = "";
        for (int j = 0; j < res[i].size(); j++)
        {
            str += to_string(res[i][j]);
            if (j != res[i].size() - 1)
                str += "->";
        }
        ans.push_back(str);
    }
    return ans;
}

int main()
{

    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(5);
    vector<string> paths = binaryTreePaths(root);
    cout << "[";
    for (int i = 0; i < paths.size() - 1; i++)
        cout << paths[i] << ",";
    cout << paths[paths.size() - 1];
    cout << "]";
    return 0;
}