二叉搜索树与双向链表

题目
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

分析
二叉搜索树转变为排序的双向链表，即将二叉搜索树按照中序遍历。中序遍历的结果即是排好序的结果，将中序遍历时的每一个节点的left和right进行调整便可实现排好序的双向链表

代码

import java.util.Stack;

public class Solution {

    public static void main(String[] args) {
        // 创建根节点
        TreeNode root = new TreeNode(6); 
        Solution solution = new Solution();
        int[] a = { 4, 7, 2, 5};
        // 插入节点
        for (int i = 0; i < a.length; i++) { 
            solution.initTree(root, a[i]);
        }
        
        solution.inFindDiGui(root);
        System.out.println();
        solution.inFindNoDiGui(root);
        System.out.println();
        TreeNode head = solution.Convert(root);
        TreeNode node = head;
        while(node != null){
            System.out.print(node.val+"->");
            node = node.right;
        }

    }
    
    // 将二叉搜索树转换为排序的双向链表
    public TreeNode Convert(TreeNode pRootOfTree) {
        TreeNode p = pRootOfTree;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        boolean flag = true;
        TreeNode head = null;
        TreeNode pre = null;
        while(p!=null || !stack.isEmpty()){
            while(p!=null){
                stack.push(p);
                p = p.left;
            }
            if(!stack.isEmpty()){
                p = stack.pop();
                // 处理头节点
                if(flag){
                    p.left = null;
                    head = p;
                    pre = p;
                    flag = false;
                } else {
                    pre.right = p;
                    p.left = pre;
                    pre = pre.right;
                }
                p = p.right;
            }
        }
        return head;
    }
    
    // 递归方式中序遍历二叉搜索树
    public void inFindDiGui(TreeNode root) {
        TreeNode p = root;
        if (null != p) {
            inFindDiGui(p.left);
            System.out.print(p.val + "->");
            inFindDiGui(p.right);
        }
    }
    
    // 非递归方式中序遍历二叉搜索树
    public void inFindNoDiGui(TreeNode root) {
        TreeNode p = root;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(p!=null || !stack.isEmpty()){
            while(p!=null){
                stack.push(p);
                p = p.left;
            }
            if(!stack.isEmpty()){
                p = stack.pop();
                System.out.print(p.val + "->");
                p = p.right;
            }
        }
        
    }
    
    // 初始化二叉搜索树
    public void initTree(TreeNode root, int val) {
        if (root != null) {
            if (val < root.val) {
                if (root.left == null) {
                    root.left = new TreeNode(val);
                } else {
                    initTree(root.left, val);
                }
            } else {
                if (root.right == null) {
                    root.right = new TreeNode(val);
                } else {
                    initTree(root.right, val);
                }
            }
        }
    }

}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }
}