988. Smallest String Starting From Leaf

T: O(n)
S: O(n)

/**
 * 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 {
    String[] res;
    public String smallestFromLeaf(TreeNode root) {
        res = new String[1];
        dfs(root, new StringBuilder(), res);
        return res[0];
    }
    private void dfs(TreeNode node, StringBuilder sb, String[] res) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            sb.append((char)(node.val + 'a'));
            String s = sb.reverse().toString();
            //System.out.println(s);
            if (res[0] == null || res[0].compareTo(s) > 0) {
                res[0] = s;
            }
            sb.reverse();
            sb.deleteCharAt(sb.length()-1);
        }

        sb.append((char)(node.val + 'a'));
        dfs(node.left, sb, res);
        dfs(node.right, sb, res);
        sb.deleteCharAt(sb.length()-1);
    }
}

/**
using same memory -> StringBuilder 
has to do backtracking,
if use String, no need backtracking, because everytime it's a new String (but waste memory) 
and create new string makes it become O(n^2) solution

so using StringBuilder is better T: O(n)

T: O(n)
S: O(n)
 */

new version

using global variable

/**
 * 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 String result;
    public String smallestFromLeaf(TreeNode root) {
        StringBuilder sb = new StringBuilder();

        dfs(root, sb);
        return result;
    }
    // using preorder
    private void dfs(TreeNode node, StringBuilder sb) {
        if (node == null) {
            return;
        }

        sb.append((char)(node.val + 'a')); // backtracking

        // reach leaf, to compare the string
        // because it's a preorder dfs, so needs to reverse String to compare, after that reverse back
        if (node.left == null && node.right == null) {
            String s = sb.reverse().toString();

            if (result == null || s.compareTo(result.toString()) < 0) {
                result = s;
            }
            sb.reverse();
        }

        dfs(node.left, sb);
        dfs(node.right, sb);
        sb.deleteCharAt(sb.length()-1); // backtracking (because we use StringBuilder, same memory)
    }
}

no using global, but really hard to know to use sb.setLength(0)

/**
 * 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 {
    public String smallestFromLeaf(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        StringBuilder result = new StringBuilder();

        dfs(root, sb, result);
        return result.toString();
    }
    // using preorder
    private void dfs(TreeNode node, StringBuilder sb, StringBuilder result) {
        if (node == null) {
            return;
        }

        sb.append((char)(node.val + 'a')); // backtracking

        // reach leaf, to compare the string
        // because it's a preorder dfs, so needs to reverse String, then backtracing it to try
        if (node.left == null && node.right == null) {
            String s = sb.reverse().toString();

            if (result.length() == 0 || s.compareTo(result.toString()) < 0) {
                result.setLength(0);
                result.append(s);
            }
            sb.reverse();
        }

        dfs(node.left, sb, result);
        dfs(node.right, sb, result);
        
        sb.deleteCharAt(sb.length()-1); // backtracking (because we use StringBuilder, same memory)
    }
}