Iterative, simple


  • 0
    V
    public IList<string> BinaryTreePaths(TreeNode root) {
            var list = new List<string>();
            if (root == null) {
                return list;
            }
    
            var t = root; var s = new Stack<TreeNode>(); var sb = new StringBuilder();
            var visited = new HashSet<TreeNode>();
            s.Push(t);
            visited.Add(t);
            sb.Append(t.val + "->");
    
            while (t != null && s.Count > 0) {
                if (t.left != null && !visited.Contains(t.left)) {
                    t = t.left; s.Push(t); visited.Add(t);
                    sb.Append(t.val + "->");
                } else if (t.right != null && !visited.Contains(t.right)) {
                    t = t.right; s.Push(t); visited.Add(t);
                    sb.Append(t.val + "->");
                } else {
                    //leaf node
                    if (t.left == null && t.right == null) {
                        list.Add(sb.ToString().Substring(0, sb.Length - 2));
                    }
                    s.Pop();
                    var textToRemove = t.val.ToString();
                    int pos = sb.ToString().LastIndexOf(textToRemove); //use lastIndex since there could be duplicate numbers in the path
                    if(pos >=0){
                        sb.Remove(pos, textToRemove.Length+2);
                    }
                    if (s.Count > 0) {
                        t = s.Peek();
                    }
                }
            }
    
            return list;
        }
    

Log in to reply
 

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