递归思路：
每次回溯的时候：
1. 如果时左子树，就找到左子树最右边那个结点与根节点相连；
2. 如果是右子树，就找到右子树中最左边那个结点与根节点相连。
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        if(pRootOfTree.left == null && pRootOfTree.right == null){
            return pRootOfTree; // 叶子结点返回自己
        }
        if(pRootOfTree.left != null){
            TreeNode left = Convert(pRootOfTree.left);
        // 找到left最右边的点和root链接
        while(left.right != null){
            left = left.right;
        }
        pRootOfTree.left = left;
        left.right = pRootOfTree;
        }
        
        if(pRootOfTree.right != null){
            TreeNode right = Convert(pRootOfTree.right);
        // 找到right最左边的点和root链接
        while(right.left != null){
            right = right.left;
        }
        pRootOfTree.right = right;
        right.left=pRootOfTree;
        }
        
        while(pRootOfTree.left != null) pRootOfTree=pRootOfTree.left;
        return pRootOfTree;
    }
}