Leetcode题 257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

All root-to-leaf paths are:

["1->2->5", "1->3"]

代码如下：

/**

 * 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 findPath(TreeNode* t,vector<int>& temp, vector<vector<int> >& record)

    {

        temp.push_back(t->val);

    	if(t->left!=NULL) findPath(t->left, temp, record);

    	if(t->right!=NULL) findPath(t->right, temp, record);

    	//到达叶子节点，就记录路径

    	if(t->left==NULL && t->right==NULL)

    	{

    	    record.push_back(temp);

    	    temp.erase(temp.end()-1);

    	    return ;

    	}

    	//中间节点返回

    	temp.erase(temp.end()-1);

    	return;

    }

    vector<string> binaryTreePaths(TreeNode* root) {

        vector<vector<int>> record;

        vector<string> srecord;

	    if(root==NULL) return srecord;

	    vector<int> temp;

	    //找到所有的路

	    findPath(root,temp,record);

	    //把所有的路按照题目要求存储

	    string stemp;

	    for(int i=0;i<record.size();i++)

	    {

	        stringstream ss;

	        for(int j=0;j<record[i].size();j++)

	        {

	            ss<<record[i][j]<<"->";

	        }

	        stemp.clear();

	        stemp=ss.str();

	        //去掉最后的"->"

	        stemp.pop_back();

	        stemp.pop_back();

	        srecord.push_back(stemp);

	    }

	    return srecord;

    }

};

巴特西

Leetcode题 257. Binary Tree Paths

最新文章

热门文章