Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.
Example:
Input:
1 / \ 2 3 \ 5
Output: ["1->2->5", "1->3"]
Explanation: All root-to-leaf paths are: 1->2->5, 1->3
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public IList<string> BinaryTreePaths(TreeNode root) {
var result = new List<string>();
var str = new List<int>();
if(root==null){
return result;
}
Helper(root,str,result);
return result;
}
private void Helper(TreeNode root,List<int> str, List<string> result){
if(root == null){
return;
}
str.Add(root.val);
if(root.left == null && root.right == null){
var sb = new StringBuilder();
for(int i=0;i<str.Count()-1;i++){
sb.Append(str[i]+"->");
}
if(str.Count()>0){
sb.Append(str[str.Count()-1]);
}
result.Add(sb.ToString());
}
Helper(root.left, str, result);
Helper(root.right, str, result);
str.RemoveAt(str.Count()-1);
}
}Time Complexity: O(2^n) we are doing backtracking
Space Complexity: O(1)
