Leetcode 988. Smallest String Starting From Leaf (二叉树遍历好题)

本文主要是介绍Leetcode 988. Smallest String Starting From Leaf (二叉树遍历好题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Smallest String Starting From Leaf
Medium
1.6K
227
Companies
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

解法1：遍历二叉树即可。
注意这里是要找到顺序最小的字符串，所以gMaxPath要初始化成ascii很大的字符串。而ascii table里面，数字<大写字母<小写字母。在前128个ascii code里面，比’z’还大的只有’{‘,’}‘,‘|’和DEL。所以可以初始化成"{}"。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:string smallestFromLeaf(TreeNode* root) {helper(root, "");return gMaxPath;}
private:string gMaxPath = "{}";//'{' or '}' > 'z'void helper(TreeNode *root, string path) {if (!root) return;path += 'a' + root->val;if (!root->left && !root->right) {reverse(path.begin(), path.end());gMaxPath = min(gMaxPath, path);return;}helper(root->left, path);helper(root->right, path);return;}
};

二刷：path改成引用。
需要注意：

如果不是引用，可以直接调用helper(root, “”)，但是如果是引用的话，需要先定义string path = “”, 然后调用helper(root, path)。
在 if (!root->left && !root->right) {}里面return前也要 path.pop_back();

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:string smallestFromLeaf(TreeNode* root) {string path = "";helper(root, path);return gMaxPath;}
private:string gMaxPath = "{}";//'{' or '}' > 'z'void helper(TreeNode *root, string &path) {if (!root) return;path += 'a' + root->val;if (!root->left && !root->right) {string tmp = path;reverse(tmp.begin(), tmp.end());gMaxPath = min(gMaxPath, tmp);path.pop_back();return;}helper(root->left, path);helper(root->right, path);path.pop_back();return;}
};