In this paper, we propose a class of growth models, named Fibonacci trees $F(t)$, with respect to the intrinsic advantage of Fibonacci sequence $\{F_{t}\}$. First, we turn out model $F(t)$ to have power-law degree distribution with exponent $γ$ greater than $3$. And then, we study analytically two significant indices correlated to random walks on networks, namely, both the optimal mean first-passage time ($OMFPT$) and the mean first-passage time ($MFPT$). We obtain a closed-form expression of $OMFPT$ using algorithm 1. Meanwhile, algorithm 2 and algorithm 3 are introduced, respectively, to capture a valid solution to $MFPT$. We demonstrate that our algorithms are able to be widely applied to many network models with self-similar structure to derive desired solution to $OMFPT$ or $MFPT$. Especially, we capture a nontrivial result that the $MFPT$ reported by algorithm 3 is no longer correlated linearly with the order of model $F(t)$.