988. Smallest String Starting From Leaf 从叶结点开始的最小字符串

@TOC

# 题目描述

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:

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.

# 解题方法

# DFS

C++代码如下：

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
string smallestFromLeaf(TreeNode* root) {
vector<string> res;
dfs(root, "", res);
sort(res.begin(), res.end());
return res[0];
}
void dfs(TreeNode* root, string path, vector<string>& res) {
if (!root->left && !root->right) {
res.push_back(char('a' + root->val) + path);
return;
}
if (root->left)
dfs(root->left, char('a' + root->val) + path, res);
if (root->right)
dfs(root->right, char('a' + root->val) + path, res);
}
};
``````

python代码如下：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def smallestFromLeaf(self, root):
"""
:type root: TreeNode
:rtype: str
"""
res = []
self.dfs(root, "", res)
res.sort()
return res[0]

def dfs(self, root, path, res):
if not root.left and not root.right:
res.append(chr(root.val + ord('a')) + path)
return
if root.left:
self.dfs(root.left, chr(root.val + ord('a')) + path, res)
if root.right:
self.dfs(root.right, chr(root.val + ord('a')) + path, res)
``````

# BFS

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
string smallestFromLeaf(TreeNode* root) {
queue<pair<TreeNode*, string>> q;
q.push({root, ""});
vector<string> res;
while (!q.empty()) {
auto h = q.front(); q.pop();
TreeNode* node = h.first;
string path = h.second;
if (!node->left && !node->right) {
res.push_back(char(node->val + 'a') + path);
continue;
}
if (node->left)
q.push({node->left, char(node->val + 'a') + path});
if (node->right)
q.push({node->right, char(node->val + 'a') + path});
}
sort(res.begin(), res.end());
return res[0];
}
};
``````

python版本的BFS如下。

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def smallestFromLeaf(self, root):
"""
:type root: TreeNode
:rtype: str
"""
q = collections.deque()
q.append((root, ""))
res = []
while q:
node, path = q.popleft()
if not node.left and not node.right:
res.append(chr(node.val + ord('a')) + path)
continue
if node.left:
q.append((node.left, chr(node.val + ord('a')) + path))
if node.right:
q.append((node.right, chr(node.val + ord('a')) + path))
res.sort()
return res[0]
``````

# 日期

2019 年 2 月 20 日 —— 少刷知乎多做题