链表六：二叉搜索树与双向链表

/**
 * 题目：二叉搜索树与双向链表
 * 描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向
 * 方案：在中序遍历中添加前驱结点
 * */

public class Six {

    /**
     * 前序遍历
     * */
    public static void two(BinaryTreeNode node) {
        if (node == null) {
            return;
        }
        System.out.println(node.var);
        one(node.left);
        one(node.right);
    }
    /**
     * 中序遍历,使用如下方法在牛客网运行得不到结果
     * */

    BinaryTreeNode head = null;//用来记录

    BinaryTreeNode realhead = null;
    @SuppressWarnings("unused")

    public static void one(BinaryTreeNode node) {
       if (node == null) {
            return;
        }
        one(node.left);
        if(head == null) {
            head = node;
            realhead = node;
        }else {
            head.right = node;
            node.left = head;
            head = node;
        }
        one(node.right);
    
    }
    /**
     * 后序遍历
     * */
    public static void three(BinaryTreeNode node) {
        if (node == null) {
            return;
        }
        one(node.left);
        one(node.right);
        System.out.println(node.var);
    }

    public static void main(String[] args) {
        BinaryTreeNode nodeRoot = new BinaryTreeNode();
        nodeRoot.var = 10;
        BinaryTreeNode nodeOne = new BinaryTreeNode();
        nodeOne.var = 6;
        BinaryTreeNode nodeTwo = new BinaryTreeNode();
        nodeTwo.var = 4;
        BinaryTreeNode nodeThree = new BinaryTreeNode();
        nodeThree.var = 8;
        BinaryTreeNode nodefour = new BinaryTreeNode();
        nodefour.var = 14;
        BinaryTreeNode nodeFive = new BinaryTreeNode();
        nodeFive.var = 12;
        BinaryTreeNode nodeSix = new BinaryTreeNode();
        nodeSix.var = 16;
        nodeRoot.left = nodeOne;
        nodeRoot.right = nodefour;
        nodeOne.left = nodeTwo;
        nodeOne.right = nodeThree;
        nodefour.left = nodeFive;
        nodefour.right = nodeSix;
        
        one(nodeRoot);
    }
    static class BinaryTreeNode{    
        int var;
        BinaryTreeNode left;
        BinaryTreeNode right;
    }
}

 

BinaryTreeNode pre;//在这个方法里面表示当前节点的前一个节点
BinaryTreeNode head; //头结点；
public BinaryTreeNode find(BinaryTreeNode node ){
　　if(node == null) return;
　　find(node.left);
　　node.left = pre;
　　if(pre != null )  
      pre.right = node;
      pre = node;
   if(head == null ) head = node; 
　　find(node.right);
　　return head;
}