算法题（十九）：搜索二叉树转双链表

题目描述

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

输入输出示例：

{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，遍历过程中，转接结点的左右结点。示例解析图如下。

---

代码

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;
	}

}