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

DFS

Straight Forward Approach

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public IList<string> BinaryTreePaths(TreeNode root) {
        var list = new List<string>();
        if(root == null)
            return list;
        Helper(root,"",list);
        return list;
    }
    public void Helper(TreeNode root,string path,List<string> list)
    {
        if(root.left == null && root.right == null)
        {
            list.Add(path + root.val);
        }
        if(root.left != null)
        {
            Helper(root.left,path + root.val + "->",list);
        }
        if(root.right != null)
        {
            Helper(root.right,path+root.val+"->",list);
        }
    }
}

String concatenation is too costly, so too avoid here. We want to move to StringBuilder with simple trick.

When using StringBuilder, We can just keep track of the length of the StringBuilder before we append anything to it before recursion and afterwards set the length back. Another trick is when to append the “->”, since we don’t need the last arrow at the end of the string, we only append it before recurse to the next level of the tree. Hope the solution helps!

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public IList<string> BinaryTreePaths(TreeNode root) {
        var list = new List<string>();
        if(root == null)
            return list;
        StringBuilder sb = new StringBuilder();
        Helper(root,sb,list);
        return list;
    }
    public void Helper(TreeNode root,StringBuilder sb,List<string> list)
    {
        //Base Condition
        if(root == null)
            return;
        
        int len = sb.Length;
        sb.Append(root.val);
        if(root.left == null && root.right == null)
        {
            list.Add(sb.ToString());
        }
        else
        {
            sb.Append("->");
            Helper(root.left,sb,list);
            Helper(root.right,sb,list);
        }
        sb.Length = len;
    }
}


Th tricky part here is sb.Length. Assigning len back to sb.Length. To understand the program well, take your note and trace the problem with this solution. You would get an better idea, so it will help you to solve future problems.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s