本文共 883 字，大约阅读时间需要 2 分钟。

题目

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

思路

这道题抽象为树模型后就是：求一颗二叉树从根结点到达叶子结点的路径总数。

因为每次可能的选择都只有两个，犹如二叉树的两个分支。栗如：

对于数字 13 ，你第一次可以只选择一位，那就是 1 ，翻译成字符就是 b；你也可以两位都选，那就是 13 , 翻译成字符为 n。

所以最多就只有两个选择：走左子树或走右子树，走到叶子结点就返回 1 ，代表这条路径可以到达终点。

转载自：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-hui-su-dong-tai/

代码

class Solution {public:    int backtrace(string &str,int pos){        int len = str.size();        if(len == pos){            return 1;        }        if(str[pos] == '0' || pos == len - 1 || str.substr(pos,2) > "25" ){            return backtrace(str,pos+1);        }        return backtrace(str,pos+1) + backtrace(str,pos+2);    }    int translateNum(int num) {        string str = to_string(num);        return backtrace(str, 0);    }};

转载地址：https://blog.csdn.net/hanmin822/article/details/105854268 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！