leetCode257.BinaryTreePaths二叉树路径
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: vectorbinaryTreePaths(TreeNode* root) { vector result; vector temp; stack 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< 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
网页名称:leetCode257.BinaryTreePaths二叉树路径
浏览地址:http://scyanting.com/article/pegedc.html