golang 解法, 执行用时: 4 ms, 内存消耗: 4.3 MB, 提交时间: 2023-06-13 09:31:46

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func smallestFromLeaf(root *TreeNode) string {
	if root == nil {
		return ""
	}
	var res string
	var dfs func(root *TreeNode, str string)
	dfs = func(root *TreeNode, str string) {
		//当前字符串
		str = string('a'+root.Val) + str
		//终止条件 叶子节点，跟当前res存储值比较
		if root.Left == nil && root.Right == nil {
			if res == "" {
				res = str
				return
			}
			if res > str {
				res = str
				return
			}
		}
		//继续向下遍历，收集路径字符
		if root.Left != nil {
			dfs(root.Left, str)
		}
		if root.Right != nil {
			dfs(root.Right, str)
		}
	}
	dfs(root, "")
	return res
}

python3 解法, 执行用时: 44 ms, 内存消耗: 17.7 MB, 提交时间: 2023-06-13 09:30:47

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
        self.ans = "~"

        def dfs(node: TreeNode, A: List[str]) -> None:
            if node:
                A.append(chr(node.val + ord('a')))
                if not node.left and not node.right:
                    self.ans = min(self.ans, "".join(reversed(A)))

                dfs(node.left, A)
                dfs(node.right, A)
                A.pop()

        dfs(root, [])
        return self.ans

java 解法, 执行用时: 1 ms, 内存消耗: 42.4 MB, 提交时间: 2023-06-13 09:29:20

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    String ans = "~";
    public String smallestFromLeaf(TreeNode root) {
        dfs(root, new StringBuilder());
        return ans;
    }

    public void dfs(TreeNode node, StringBuilder sb) {
        if (node == null) return;
        sb.append((char)('a' + node.val));

        if (node.left == null && node.right == null) {
            sb.reverse();
            String S = sb.toString();
            sb.reverse();

            if (S.compareTo(ans) < 0)
                ans = S;
        }

        dfs(node.left, sb);
        dfs(node.right, sb);
        sb.deleteCharAt(sb.length() - 1);
    }
}

cpp 解法, 执行用时: 8 ms, 内存消耗: 19.1 MB, 提交时间: 2023-06-13 09:28:49

/**
 * 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 res;
    string smallestFromLeaf(TreeNode* root) {
        dfs(root,"");
        return res;
    }

    void dfs(TreeNode* root,string path)
    {
        if(!root->left&&!root->right){
            path.push_back(root->val+'a');
            reverse(path.begin(),path.end());
            if(res.empty())res=path;
            else if(path<res)res=path;
            return;
        }
        if(root->left)dfs(root->left,path+char(root->val+'a'));
        if(root->right)dfs(root->right,path+char(root->val+'a'));
    }
};