C# Iterative solution


  • 0
    Z

    The main idea is to build a parent dictionary and a list of leaf node. Then add all paths to the result.
    Although time is pretty long, you can add all kind of optimization such as streambuilder.

    '''

    public class Solution {
    public IList<string> BinaryTreePaths(TreeNode root) {
    List<string> res = new List<string>();
    if (root == null) return res;
    Queue<TreeNode> q = new Queue<TreeNode>();
    Dictionary<TreeNode, TreeNode> p = new Dictionary<TreeNode,TreeNode>();
    List<TreeNode> leaf = new List<TreeNode>();
    q.Enqueue(root);
    p.Add(root, null);
    TreeNode r1 = null;
    while(q.Count()>0)
    {
    int levelCount = q.Count();
    for(int i = 0; i < levelCount; i++)
    {
    r1 = q.Dequeue();
    if (r1.left!=null)
    {
    p.Add(r1.left, r1);
    q.Enqueue(r1.left);
    }
    if (r1.right!=null)
    {
    p.Add(r1.right, r1);
    q.Enqueue(r1.right);
    }
    if (r1.left==null && r1.right == null)
    leaf.Add(r1);
    }
    }
    foreach(var item in leaf)
    {
    r1 = p[item];
    string s = item.val.ToString();
    while (r1!= null)
    {
    s = r1.val +"->" + s;
    r1 = p[r1];
    }
    res.Add(s);
    }
    return res;
    }
    }
    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.