leetCode 257. Binary Tree Paths 二叉树路径

257. Binary Tree Paths

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

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

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

思路：

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

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

代码如下：

/**
 * 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:
    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中。
                    int len = s.size();
                    for(int i = 0; i < len; i++)
                    {
                        temp.push_back(s.top());
                        s.pop();
                    }
                    
                    string strTemp = "";
                    for(int i = temp.size() - 1; i >= 0;i--)
                    {
                        stringstream ss;
                        ss<<temp[i]->val;
                        strTemp += ss.str();
                        if(i >= 1)
                        {
                            strTemp.append("->");
                        }
                    }
                    result.push_back(strTemp);
                    
                    for(int i = 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;
                }
                else
                    p = p->right;
            }
        }
        
        return result;
    }
};

2016-08-07 01:47:24