[LeetCode] 988. Smallest String Starting From Leaf

 轉自LeetCode

You are given the root of a binary tree where each node has a value in the range [0, 25] representing the letters 'a' to 'z'.

Return 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: root = [0,1,2,3,4,3,4]
Output: "dba"

Example 2:

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

Example 3:

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

 

Constraints:

• The number of nodes in the tree is in the range [1, 8500].
• 0 <= Node.val <= 25

Solution

BST 加上要找極值，用 DFS 解

這題比較需要注意的地方，應該是 lexicographical order 和答案字串的順序

kolin 有提供一個 compareTo 的 function 可以使用，就是用 lexicographical order 比較

kotlin

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	var ans = ('z'+ 1).toString() // any char that bigger than 'z'
	fun smallestFromLeaf(root: TreeNode?): String {
	dfs(root, "")
	return ans
	}
	fun dfs(node: TreeNode?, path: String) {
	when {
	node == null -> return
	node!!.left == null && node!!.right == null -> {
	if (ans.compareTo(('a' + node!!.`val`) + path) > 0) {
	ans = ('a' + node!!.`val`) + path
	}
	}
	else -> {
	dfs(node!!.left, ('a' + node!!.`val`) + path)
	dfs(node!!.right, ('a' + node!!.`val`) + path)
	}
	}
	}
	}

view raw smallest_string_starting_from_leaf.kt hosted with ❤ by GitHub