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 0
represents '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:
- The number of nodes in the given tree will be between
1
and1000
. - Each node in the tree will have a value between
0
and25
.
Solution: Recursion
Time complexity: O(n^2)
Space complexity: O(n^2)
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua, running time: 0 ms class Solution { public: 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; } }; |
Python3
1 2 3 4 5 6 7 |
class Solution: def smallestFromLeaf(self, root: 'TreeNode') -> 'str': if not root: return '~' c = chr(root.val + ord('a')) if not root.left and not root.right: return c return min(self.smallestFromLeaf(root.left), self.smallestFromLeaf(root.right)) + c |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment