class Untitled {

	public static void main(String[] args) {

		TreeNode node1 = new TreeNode(10);

		TreeNode node2 = new TreeNode(6);

		TreeNode node3 = new TreeNode(14);

		TreeNode node4 = new TreeNode(4);

		TreeNode node5 = new TreeNode(8);

		TreeNode node6 = new TreeNode(12);

		TreeNode node7 = new TreeNode(16);

		node1.setNode(node2,node3);

		node2.setNode(node4,node5);

		node3.setNode(node6,node7);

		Solution s = new Solution();

		TreeNode p = s.Convert(node1);

		while(p.right!=null){

			System.out.println(p.val);

			p = p.right;

		}

	}

}

	//树的定义

class TreeNode {

    int val = 0;

    TreeNode left = null;

    TreeNode right = null;

    public TreeNode(int val) {

        this.val = val;

    }

	public void setNode(TreeNode node1,TreeNode node2){

		this.left = node1;

		this.right = node2;

	}

}

//解方法

class Solution {

    public TreeNode Convert(TreeNode root) {

        if(root==null)

            return null;

        if(root.left==null&&root.right==null)

            return root;

// 1.将左子树构造成双链表，并返回链表头节点

        TreeNode left = Convert(root.left);

        TreeNode p = left;

 // 2.定位至左子树双链表最后一个节点

        while(p!=null&&p.right!=null){

            p = p.right;

        }

// 3.如果左子树链表不为空的话，将当前root追加到左子树链表

        if(left!=null){

            p.right = root;

            root.left = p;

        }

// 4.将右子树构造成双链表，并返回链表头节点

        TreeNode right = Convert(root.right);

 // 5.如果右子树链表不为空的话，将该链表追加到root节点之后

        if(right!=null){

            right.left = root;

            root.right = right;

        }

        return left!=null?left:root;

    } 

}

public class Solution {

    TreeNode realHead = null;

    TreeNode head = null;

    public TreeNode Convert(TreeNode root) {

        ConvertHelp(root);

        return realHead;

    }

    public void ConvertHelp(TreeNode root){

        if(root==null)

            return;

        ConvertHelp(root.left);

        if(realHead==null){

            head = root;

            realHead = root;

        }else{

            head.right = root;

            root.left = head;

            head = root;

        }

        ConvertHelp(root.right);

    }

}