Friday, October 16, 2015

[Leetcode] Binary Tree Paths, Solution

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"]

[Thought]
这个主要就是实现题。对树进行深度遍历,在遍历的过程中保存访问节点,当遍历到叶节点的时候,打印出来路径即可。

[Code]
1:  class Solution {  
2:  public:  
3:    vector<string> binaryTreePaths(TreeNode* root) {  
4:      vector<string> paths;  
5:      vector<int> nodes;  
6:      getAllPaths(root, nodes, paths);       
7:      return paths;  
8:    }  
9:    void getAllPaths(TreeNode* node, vector<int>& nodes,vector<string>& paths) {  
10:      if(node == NULL) {  
11:        return;  
12:      }  
13:      if(node->left== NULL && node->right == NULL) {  
14:        stringstream ss;  
15:        for(int i =0; i< nodes.size(); i++) {  
16:          ss << nodes[i] << "->";  
17:        }  
18:        ss << node->val;  
19:        paths.push_back(ss.str());  
20:        return;  
21:      }  
22:      nodes.push_back(node->val);  
23:      getAllPaths(node->left, nodes, paths);  
24:      getAllPaths(node->right, nodes, paths);  
25:      nodes.pop_back();  
26:    }  
27:  };  

Github: https://github.com/codingtmd/leetcode/blob/master/src/Binary%20Tree%20Paths.cpp

No comments: