package LeetCode;

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

public class LeetCode257 {

    /// 257. Binary Tree Paths
    /// https://leetcode.com/problems/binary-tree-paths/description/
    /// : O(n), n
    /// : O(h), h

    // Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /**
     * 
     * @param root
     * @return
     */
    public List binaryTreePaths(TreeNode root) {

        ArrayList res = new ArrayList();

        if (root == null)
            return res;

        //  1
        //    /
        //   2

        if (root.left == null && root.right == null) {
            res.add(Integer.toString(root.val));
            return res;
        }

        List leftPaths = binaryTreePaths(root.left);
        for (String s : leftPaths) {
            StringBuilder sb = new StringBuilder(Integer.toString(root.val));
            sb.append("->");
            sb.append(s);
            res.add(sb.toString());
        }

        List rightPaths = binaryTreePaths(root.right);
        for (String s : rightPaths) {
            StringBuilder sb = new StringBuilder(Integer.toString(root.val));
            sb.append("->");
            sb.append(s);
            res.add(sb.toString());
        }

        return res;
    }
}