Predicting traffic flow plays an important role in reducing traffic congestion and improving transportation efficiency for smart cities. Traffic Flow Prediction (TFP) in the smart city requires efficient models, highly reliable networks, and data privacy. As traffic data, traffic trajectory can be transformed into a graph representation, so as to mine the spatio-temporal information of the graph for TFP. However, most existing work adopt a central training mode where the privacy problem brought by the distributed traffic data is not considered. In this paper, we propose a Federated Deep Learning based on the Spatial-Temporal Long and Short-Term Networks (FedSTN) algorithm to predict traffic flow by utilizing observed historical traffic data. In FedSTN, each local TFP model deployed in an edge computing server includes three main components, namely Recurrent Long-term Capture Network (RLCN) module, Attentive Mechanism Federated Network (AMFN) module, and Semantic Capture Network (SCN) module. RLCN can capture the long-term spatial-temporal information in each area. AMFN shares short-term spatio-temporal hidden information when it trains its local TFP model by the additive homomorphic encryption approach based on Vertical Federated Learning (VFL). We employ SCN to capture semantic features such as irregular non-Euclidean connections and Point of Interest (POI). Compared with existing baselines, several simulations are conducted on practical data sets and the results prove the effectiveness of our algorithm.