LeetCode刷题记录14——257. Binary Tree Paths(easy)
LeetCode刷题记录14——257. Binary Tree Paths(easy)
目录
前言
数据结构感觉理论简单,实践起来很困难。
题目
给定一个二叉树,输出所有的根节点到叶节点的路径(以字符串的形式返回)
语言
C++
思路
学了数据结构,所以一看到这种输出路径的,就想到了先序遍历、中序遍历、后序遍历的递归方法。
首先写一个方法test,这个方法就是用来递归求路径的,形参有结点指针、字符串str和路径paths。首先判断结点指针是否为空,不为空则将这个结点的value加到字符串str后面,当然,他给的是int型的value,所以得通过to_string转化成字符串型,这样才能不断的加在字符串str的尾巴后面。接着分3种情况:
-
如果结点的左孩子右孩子指针均为空,那么说明他没有孩子,则直接将str加在vector的尾部
-
如果左孩子指针不为空,那么就递归调用test(root->left,str+"->",paths)
-
如果右孩子指针不为空,那么就递归调用test(root->right,str+"->",paths)
最后在他所给的方法中定义个vector<string>paths,然后调用方法test(root,"",paths),就能返回paths。
源码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void test(TreeNode* root,string str,vector<string> &paths){
if(root!=NULL) {
str=str+to_string(root->val);
if(root->left==NULL&&root->right==NULL)
paths.push_back(str);
if(root->left!=NULL)
test(root->left,str+"->",paths);
if(root->right!=NULL)
test(root->right,str+"->",paths);
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string>paths;
test(root,"",paths);
return paths;
}
};
后记
做这题我先去查了C++int型如何转为string,然后就知道了to_string;接着考虑到没有孩子的情况,所以又去查了如何在尾部加上数据,所以知道了push_back这个方法。