988. 从叶结点开始的最小字符串

988. 从叶结点开始的最小字符串

---

C代码：DFS

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/// 叶子节点// 每一层用一个pathTop、遇到叶子节点就判断一次；建立一个ans字符串，每次叶子节点与之比较// 建一个全局的数组，最后再reverse#define MAX_LEN 8501char* tmp;    // reverse接收用, 末尾加'\0'
char* path;   // 全局路径, 用pathTop维系
char* ans;    // strcat自动加'\0'char* reverse(int pathTop) {for (int i = 0; i < pathTop; ++i) {tmp[i] = path[pathTop - i -1];}tmp[pathTop] = '\0';return tmp;
}void dfs(struct TreeNode* root, int pathTop) {if (root == NULL) {return;}path[pathTop++] = root->val + 'a';  // 先序遍历if (root->left == NULL && root->right == NULL) {char* tmp = reverse(pathTop);if (strlen(ans) == 0 || strcmp(ans, tmp) > 0) {  // ans 大于 tmp 返回 >0ans[0] = '\0';strcat(ans, tmp);}}dfs(root->left, pathTop);dfs(root->right, pathTop);
}char * smallestFromLeaf(struct TreeNode* root){path = (char*)malloc(sizeof(char) * MAX_LEN);tmp = (char*)malloc(sizeof(char) * MAX_LEN);ans = (char*)malloc(sizeof(char) * MAX_LEN);   ans[0] = '\0';dfs(root, 0);return ans;
}