二叉搜索树转双向链表

解题核心思想：查找左子树的最右节点，和右子树的最左节点，然后将其与根节点相连，连接时left指向小的，right指向大的，根节点和查找来的记得点均需要要进行修改。
注意：最后返回值要是最左边的那一个节点，不能直接返回原来的root节点

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    // 递归查找子树的最左或最右节点
    TreeNode f(TreeNode root, int leftOrRight){
        // 如果没有节点了，那就返回自己
        if(root.left==null&&root.right==null){
            return root;
        }
        // 如果左子树不为空，那就递归找左子树的最右节点
        if(root.left!=null){
            TreeNode tmpNode = f(root.left, 0);
            // 找到后，双向修改其指针
            root.left = tmpNode;
            tmpNode.right = root;
        }
        // 如果右子树不为空，那就递归找右子树的最左节点
        if(root.right!=null){
            TreeNode tmpNode = f(root.right, 1);
            // 找到后，双向修改其指针
            root.right = tmpNode;
            tmpNode.left = root;
        }
        // 如果当前子树是上一个根节点的左子树，那么返回的要么就是当前子树根节点的right，如果right为空则返回root
        if(leftOrRight==0){
            if(root.right==null){
                return root;
            }else {
                // 这个root已经是上一级返回了的
                return root.right;
            }
        // 右子树同理
        }else {
            if(root.left==null){
                return root;
            }else {
                return root.left;
            }
        }


    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        if(pRootOfTree.left!=null){
            TreeNode tmpNode = f(pRootOfTree.left, 0);
            pRootOfTree.left = tmpNode;
            tmpNode.right = pRootOfTree;

        }
        if(pRootOfTree.right!=null){
            TreeNode tmpNode = f(pRootOfTree.right, 1);
            pRootOfTree.right = tmpNode;
            tmpNode.left = pRootOfTree;
        }
        TreeNode ans = pRootOfTree;
        while(ans.left!=null){
            ans = ans.left;
        }
        return ans;
    }
}