# Question

Formatted question description: https://leetcode.ca/all/257.html

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

Example 1:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]


Example 2:

Input: root = [1]
Output: ["1"]


Constraints:

• The number of nodes in the tree is in the range [1, 100].
• -100 <= Node.val <= 100

# Algorithm

In the recursive function, when a leaf node is encountered, there is no left or right child node, then a complete path has been formed at this time, add the current leaf node and save it in the result, and then backtrack.

# Code

• import java.util.ArrayList;
import java.util.List;

public class Binary_Tree_Paths {

public static void main (String[] args) {

Binary_Tree_Paths out = new Binary_Tree_Paths();
Solution s = out.new Solution();

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(5);

System.out.println(s.binaryTreePaths(root));

Solution_iteration si = out.new Solution_iteration();
System.out.println(si.binaryTreePaths(root));
}

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

class Solution_iteration {

public List<Integer> binaryTreePaths(TreeNode root) {

if (root == null) {
return null;
}

Binary_Tree_Preorder_Traversal preOderIteration = new Binary_Tree_Preorder_Traversal();

Binary_Tree_Preorder_Traversal.Solution preOrderSolution = preOderIteration.new Solution();

List<Integer> result = preOrderSolution.preorderTraversal(root);

return result;
}
}

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<String>();

if(root == null) {
return result;
}

helper(new String(), root, result);

return result;
}

public void helper(String current, TreeNode root, List<String> result) {
if(root.left == null && root.right == null) {
}

if(root.left != null) {
helper(current + root.val + "->", root.left, result);
}

if(root.right != null) {
helper(current + root.val + "->", root.right, result);
}
}

}
}

############

/**
* Definition for a binary tree node.
* public 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;
*     }
* }
*/
class Solution {
private List<String> ans;
private List<String> t;

public List<String> binaryTreePaths(TreeNode root) {
ans = new ArrayList<>();
t = new ArrayList<>();
dfs(root);
return ans;
}

private void dfs(TreeNode root) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
}
dfs(root.left);
dfs(root.right);
t.remove(t.size() - 1);
}
}

• // OJ: https://leetcode.com/problems/binary-tree-paths/
// Time: O(NH)
// Space: O(H^2)
class Solution {
private:
vector<string> v;
void preorder(TreeNode *root, string path) {
path += to_string(root->val);
if (!root->left && !root->right) {
v.push_back(path);
return;
}
path += "->";
if (root->left) preorder(root->left, path);
if (root->right) preorder(root->right, path);
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
if (!root) return {};
preorder(root, "");
return v;
}
};

• # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
def dfs(root):
if root is None:
return
t.append(str(root.val))
if root.left is None and root.right is None:
ans.append('->'.join(t))
dfs(root.left)
dfs(root.right)
t.pop()

t = []
ans = []
dfs(root)
return ans

############

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
# @param {TreeNode} root
# @return {string[]}
def binaryTreePaths(self, root):
def helper(root, path, res):
if root:
path.append(str(root.val))
left = helper(root.left, path, res)
right = helper(root.right, path, res)
if not left and not right:
res.append("->".join(path))
path.pop()
return True

res = []
helper(root, [], res)
return res


• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func binaryTreePaths(root *TreeNode) []string {
var ans []string
var t []string
var dfs func(root *TreeNode)
dfs = func(root *TreeNode) {
if root == nil {
return
}
t = append(t, strconv.Itoa(root.Val))
if root.Left == nil && root.Right == nil {
ans = append(ans, strings.Join(t, "->"))
}
dfs(root.Left)
dfs(root.Right)
t = t[:len(t)-1]
}
dfs(root)
return ans
}

• /**
* Definition for a binary tree node.
* class TreeNode {
*     val: number
*     left: TreeNode | null
*     right: TreeNode | null
*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.left = (left===undefined ? null : left)
*         this.right = (right===undefined ? null : right)
*     }
* }
*/

function binaryTreePaths(root: TreeNode | null): string[] {
let ans = [];
let t = [];
function dfs(root) {
if (!root) return;
t.push(String(root.val));
if (!root.left && !root.right) ans.push(t.join('->'));
dfs(root.left);
dfs(root.right);
t.pop();
}
dfs(root);
return ans;
}