Blogs Hub

by Sumit Chourasia | Oct 06, 2020 | Category :coding | Tags : algorithm binary-tree data-structure easy leetcode tree

Binary Tree Paths - Tree - Easy - LeetCode

Binary Tree Paths - Tree - Easy - LeetCode

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)

Contributed By: Sumit Chourasia
Subarray Sum Equals K - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Decode XORed Array - Array - Easy - LeetCode