描述
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
All root-to-leaf paths are:
分析
树的深度优先遍历。
解决方案1(C++)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
|
class Solution { public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; if(root == NULL) { return result; } path(root, result, to_string(root->val)); return result; } void path(TreeNode* root, vector<string>& result, string str_buff) { if(root->left==NULL && root->right==NULL) { result.push_back(str_buff); } if(root->left != NULL) { path(root->left, result, str_buff+"->"+to_string(root->left->val)); } if(root->right != NULL) { path(root->right, result, str_buff+"->"+to_string(root->right->val)); } } };
|
解决方案2(Java)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
|
public class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> result = new ArrayList<>(); if(root == null) { return result; } String str_buff = new String(); path(root, result, (root.val)+""); return result; } private void path(TreeNode root, List<String> result, String str_buff) { if(root.left == null && root.right == null) { result.add(str_buff.toString()); } if(root.left != null) { path(root.left, result, str_buff+"->"+(root.left.val)); } if(root.right != null) { path(root.right, result, str_buff+"->"+(root.right.val)); } } }
|
解决方案3(Python)
相关问题
(M) Path Sum II