988. Smallest String Starting From Leaf

Link

Solution

這題想法很簡單，可以想到。

但程式很難想的可以通過各種test case。

我用StringBuilder怎麼寫都錯。

但參考discussion用 String就可以寫出沒問題的solution

  public String smallestFromLeaf(TreeNode root) {
        return dfs(root, "");
    }
    
    public String dfs(TreeNode node, String suffix){
        if(node == null) return suffix;
        
        suffix = (char)(node.val + 'a') + suffix;
        
        if(node.left == null && node.right == null){
            return suffix;
        }
        if(node.left == null){
            return dfs(node.right, suffix);
        }
        if(node.right == null){
            return dfs(node.left, suffix);
        }
        
        
        String left = dfs(node.left, suffix);
        String right = dfs(node.right, suffix);
        if(left.compareTo(right) > 0){
            return right;
        }
        else{
            return left;
        }
    }