257. Binary Tree Paths

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

For example, given the following binary tree:


1/\23\5


All root-to-leaf paths are:

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

思路：

1.采用二叉树的后序遍历非递归版

2.在叶子节点的时候处理字符串

代码如下：

/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode(intx):val(x),left(NULL),right(NULL){}*};*/classSolution{public:vector<string>binaryTreePaths(TreeNode*root){vector<string>result;vector<TreeNode*>temp;stack<TreeNode*>s;TreeNode*p,*q;q=NULL;p=root;while(p!=NULL||s.size()>0){while(p!=NULL){s.push(p);p=p->left;}if(s.size()>0){p=s.top();if(NULL==p->left&&NULL==p->right){//叶子节点已经找到，现在栈里面的元素都是路径上的点//将栈中元素吐出放入vector中。intlen=s.size();for(inti=0;i<len;i++){temp.push_back(s.top());s.pop();}stringstrTemp="";for(inti=temp.size()-1;i>=0;i--){stringstreamss;ss<<temp[i]->val;strTemp+=ss.str();if(i>=1){strTemp.append("->");}}result.push_back(strTemp);for(inti=temp.size()-1;i>=0;i--){s.push(temp[i]);}temp.clear();}if((NULL==p->right||p->right==q)){q=p;s.pop();p=NULL;}elsep=p->right;}}returnresult;}};

2016-08-07 01:47:24