LeetCode 988 - Smallest String Starting From Leaf

https://leetcode.com/problems/smallest-string-starting-from-leaf/

Given the root of a binary tree, each node has a value from 0 to 25 representing the letters 'a' to 'z': a value of 0represents 'a', a value of 1 represents 'b', and so on.

Find the lexicographically smallest string that starts at a leaf of this tree and ends at the root.

(As a reminder, any shorter prefix of a string is lexicographically smaller: for example, "ab" is lexicographically smaller than "aba".  A leaf of a node is a node that has no children.)

Example 1:

Input: [0,1,2,3,4,3,4]
Output: "dba"

Example 2:

Input: [25,1,3,1,3,0,2]
Output: "adz"

Example 3:

Input: [2,2,1,null,1,0,null,0]
Output: "abc"

Note:

1. The number of nodes in the given tree will be between 1 and 1000.
2. Each node in the tree will have a value between 0 and 25

X.

  public String smallestFromLeaf(TreeNode root) {

    if (root == null)

      return "";

    StringBuilder ans = dfs(root);

    return ans == null ? "" : ans.toString();

  }

  public StringBuilder dfs(TreeNode node) {

    if (null == node) {

      return null;

    }

    char ch = (char) ('a' + node.val);

    StringBuilder left = dfs(node.left);

    StringBuilder right = dfs(node.right);

    if (left == null && right == null) { // leaf

      return new StringBuilder().append(ch);

    } else if (left == null || right == null) {

      return left != null ? left.append(ch) : right.append(ch);

    } else { // both are not null

      if (left.toString().compareTo(right.toString()) < 0) {

        return left.append(ch);

      } else {

        return right.append(ch);

      }

    }

  }

https://leetcode.com/problems/smallest-string-starting-from-leaf/discuss/231095/Python-short-recursive-solution

def smallestFromLeaf(self, node: 'TreeNode') -> 'str':
        if not node: return ''
        left = self.smallestFromLeaf(node.left)
        right = self.smallestFromLeaf(node.right)
        return (left if right == '' or (left != '' and left < right) else right) + chr(97+node.val)

X. Post Order - bottom up
http://www.noteanddata.com/leetcode-988-Smallest-String-Starting-From-Leaf-java-solution-note.html

1. 这个题目和之前的很多题目一样， 需要做bottom up 遍历， 也就是从叶节点遍历
2. 对于bottom up 遍历， 通常我们需要做递归的post order从下向上遍历，
3. 由于只需要返回一个最小的值， 那么对于任何一个节点， 我们都只需要取当前的最小值， 因为每个节点向上的值都是固定的
   区别只在于子节点上的路径， 所以，对于任意一个节点，都从子节点中取最小值

public String smallestFromLeaf(TreeNode root) {
    return dfs(root);
}

public String dfs(TreeNode node) {
    if(null == node) {
        return null;
    }
    else {
        char ch = (char)('a' + node.val);
        String left = dfs(node.left);
        String right = dfs(node.right);
        if(left == null && right == null) { // leaf
            return "" + ch;
        }
        else if(left == null || right == null) {
            return left != null ? (left + ch) : (right+ch);
        }
        else { // both are not null
            if(left.compareTo(right) < 0) {
                return left + ch;
            }
            else {
                return right + ch;
            }
        }
    }
}




https://leetcode.com/articles/smallest-string-starting-from-leaf/

• Time Complexity: We use $O(N)$ to traverse the array and maintain A [Python] or sb. Then, our reversal and comparison with the previous answer is $O(L)$, where $L$ is the size of the string we have when at the leaf.
• Space Complexity: $O(N)$. 

  String ans = "~";

  public String smallestFromLeaf(TreeNode root) {

    dfs(root, new StringBuilder());

    return ans;

  }

  public void dfs(TreeNode node, StringBuilder sb) {

    if (node == null)

      return;

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

    if (node.left == null && node.right == null) {

      sb.reverse();

      String S = sb.toString();

      sb.reverse();

      if (S.compareTo(ans) < 0)

        ans = S;

    }

    dfs(node.left, sb);

    dfs(node.right, sb);

    sb.deleteCharAt(sb.length() - 1);

  }

https://leetcode.com/problems/smallest-string-starting-from-leaf/discuss/231251/Java-2-Concise-DFS-codes-with-comment.

    private String ans = "~"; // dummy value '~' > 'z'
    public String smallestFromLeaf(TreeNode root) {
        return dfs(root, "");
    }
    private String dfs(TreeNode n, String str) {
        if (n == null) { return str; } // base case, and in case root is null.
        str = (char)(n.val + 'a') + str; // prepend current char to the path string from root.
        if (n.left == null && n.right == null && ans.compareTo(str) > 0) { ans = str; } // update ans if n is a leaf.
        dfs(n.left, str); // recursion to the left branch.
        dfs(n.right, str); // recursion to the right branch.
        return ans;
    }

If we do NOT have to return empty string "" against input root == null, we can simplify the above as follows:

    public String smallestFromLeaf(TreeNode root) {
        if (root == null) { return "~"; } // corner case with dummy value.
        char c = (char)(root.val + 'a'); // convert root.val to char.
        if (root.left == null && root.right == null) { return "" + c; } // base case: if the node is a leave, return the char associated the node.
        String lf = smallestFromLeaf(root.left) + c, rt = smallestFromLeaf(root.right) + c; // appended with the char associated with their parent. 
        return lf.compareTo(rt) < 0 ? lf : rt; //return the branch with smaller value.
    }

https://zxi.mytechroad.com/blog/tree/leetcode-988-smallest-string-starting-from-leaf/
Time complexity: O(n^2)
Space complexity: O(n^2)

  string smallestFromLeaf(TreeNode* root) {

    if (!root) return "|"; // '|' > 'z'

    const char v = static_cast<char>('a' + root->val);

    if (!root->left && !root->right) return string(1, v);

    string l = smallestFromLeaf(root->left);    

    string r = smallestFromLeaf(root->right);    

    return min(l, r) + v;

  }

https://leetcode.com/problems/smallest-string-starting-from-leaf/discuss/231102/C%2B%2B-3-lines