using System;

//using System.Collections.Generic;

using System.Linq;

//using System.Text;

//using System.Threading.Tasks;

​

namespace ConsoleApplication2

{

    public class BinaryTreeToList

    {

        public BinaryTreeToList()

        {

​

​

        }   

​

        public DoubleLinkedListNode ConvertTreeToDoubleLinkedListNode(TreeNode root)

        {

            if (root == null)

            {

                return null;

            }

            DoubleLinkedListNode res = new DoubleLinkedListNode();

            res.Index = root.Index;

            if (root.Left != null)

            {

                var newNode = ConvertTreeToDoubleLinkedListNode(root.Left);

                newNode.Previous = res;

                res.Next = newNode;

            }

            if (root.Right != null)

            {

                if (res.Next == null)

                {

                    var newNode = ConvertTreeToDoubleLinkedListNode(root.Right);

                    newNode.Previous = res;

                    res.Next = newNode;

                }

                else if (res.Next.Next == null)

                {

​

                    var newNode = ConvertTreeToDoubleLinkedListNode(root.Right);

                    newNode.Previous = res.Next;

                    res.Next.Next = newNode;

​

                }

                else

                {

                    DoubleLinkedListNode temp = res;

                    while (temp.Next != null)

                    {

                        temp = temp.Next;

                    }

                    var newNode =  ConvertTreeToDoubleLinkedListNode(root.Right);

                    newNode.Previous = temp;

                    temp.Next = newNode;

​

                }

            }

            return res;

        }

    }

​

    public class DoubleLinkedListNode

    {

        public int Index { get; set; }

        public DoubleLinkedListNode Next { get; set; }

        public DoubleLinkedListNode Previous { get; set; }

    }

}