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

输入输出示例：

{10,6,4,8,14,12,16}

from left to right:4,6,8,10,12,14,16 from right to left:16,14,12,10,8,6,4

{1,2,3,4,5}

from left to right:1,2,3,4,5 from right to left:5,4,3,2,1

{1}

from left to right:1 from right to left:1

分析
方法一：可用二叉树中序遍历方法来遍历BST，遍历过程中，转接结点的左右结点。示例解析图如下。



方法二：用递归法来求解。把左子树排成双向链表后，返回第一个结点，再把root结点接到左表后面，把右子树也排成双向链表并返回第一个结点，把右表接到root结点后面。

代码一
import java.util.Stack;

public class BST2List {

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                TreeNode root = new TreeNode(10);
                root.left = new TreeNode(6);
                root.left.left = new TreeNode(4);
                root.left.right = new TreeNode(8);
                root.right = new TreeNode(14);
                root.right.left = new TreeNode(12);
                root.right.right = new TreeNode(16);
                root = convert(root);
                while(root != null){
                        System.out.println(root.value);
                        root = root.right;
                }
        }
       
        public static TreeNode convert(TreeNode root){
                Stack<TreeNode> stack = new Stack<>();
                if(root == null){
                        return null;
                }
                stack.push(root);
                TreeNode sNode = root;
                while(sNode.left != null){
                        stack.push(sNode.left);
                        sNode = sNode.left;
                }
                TreeNode node1 = stack.pop();
                root = node1;
                if(stack.isEmpty() && root.right!=null){
                        stack.push(root.right);
                }
                while(!stack.isEmpty()){
                       
                                TreeNode node2 = stack.pop();
                                node1.right = node2;
                                node2.left = node1;
                                node1 = node2;
                                TreeNode tempNode = node2.right;
                                if(tempNode != null){
                                        stack.push(tempNode);
                                        while(tempNode.left != null){
                                                stack.push(tempNode.left);
                                                tempNode = tempNode.left;
                                        }
                                }
                       
                }
                return root;
        }

}
代码二
public class BST2List2 {

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                TreeNode root = new TreeNode(10);
                root.left = new TreeNode(6);
                root.left.left = new TreeNode(4);
                root.left.right = new TreeNode(8);
                root.right = new TreeNode(14);
                root.right.left = new TreeNode(12);
                root.right.right = new TreeNode(16);
                root = convert(root);
                while(root != null){
                        System.out.println(root.value);
                        root = root.right;
                }
        }
       
        public static TreeNode convert(TreeNode root){
                if(root == null){
                        return null;
                }
                if(root.left==null && root.right==null){
                        return root;
                }
                TreeNode left = convert(root.left);
                TreeNode p = left;
                while(p!=null && p.right != null){
                        p=p.right;
                }
                if(left != null){
                        p.right=root;
                        root.left=p;
                }
                TreeNode right = convert(root.right);
                if(right != null){
                        right.left = root;
                        root.right = right;
                }
                return left != null ? left : root;
               
        }

}

---------------------
作者：另一个我竟然存在
来源：CSDN
原文：https://blog.csdn.net/qq_24034545/article/details/83420418
版权声明：本文为博主原创文章，转载请附上博文链接！

奈斯