【Java】面试题36：二叉搜索树与双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package jianZhiOffer;
/*
 * 面试题36：二叉搜素树与双向链表
 * 题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排列的双向链表。
 * 要求不能创建任何新的节点，只能调整树中节点指针的指向
 */
public class Demo36 {
	 static class TreeNode{
		 int value;
		 TreeNode left;
		 TreeNode right;
		 public TreeNode(int v) { 
			 this.value = v; 
			 }
		 } 
	 
	 public static TreeNode convert(TreeNode root){
		 TreeNode lastNodeInList = null;
		 convertNode(root, lastNodeInList);
		 
		 if(lastNodeInList == null){
			 return null;
			 }
		 TreeNode listHead = lastNodeInList;
		 while(listHead != null && listHead.left != null){ 
			 listHead = listHead.left;
			 }
		 return listHead; 
	}
	 
	 private static void convertNode(TreeNode node, TreeNode lastNodeInList) { 
		 if(node == null){ 
			 return; 
			 }
		 TreeNode currentNode = node;
		 if(currentNode.left != null){ 
			 convertNode(currentNode.left, lastNodeInList);
			 }
		 currentNode.left = lastNodeInList; 
		 if(lastNodeInList != null){ 
			 lastNodeInList.right = currentNode;
			 }
		 lastNodeInList = currentNode;
		 if(lastNodeInList != null){
			 System.out.println("Set last = " + lastNodeInList.value); 
			 }else{
				 System.out.println("Set last = null");
				 }
		 if(currentNode.right != null){ 
			 convertNode(currentNode.right, lastNodeInList);
		 } 
	 }
	 
	 public static void main(String[] args) {
		 TreeNode root = new TreeNode(10);
		 root.left = new TreeNode(6);
		 root.right = new TreeNode(14); 
		 root.left.left = new TreeNode(4);
		 root.left.right = new TreeNode(8);
		 root.right.left = new TreeNode(12);
		 root.right.right = new TreeNode(16);
		 
		 TreeNode head = convert(root);
		 

		 }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
 * 递归方法：
 * 由于题目要求排序的双向列表，所以首先将二叉搜索树中序遍历，这里采用一个队列来存放要排序的节点，每访问一个节点将其
 * 入队，最后全部入队后队列里面是排好序的节点，队首是值最小的节点。然后开始出队，每出队一个元素，将该元素的right指向
 * 队首元素,将队首元素的left指向刚才出队的那个元素。直到队列中只有1个元素时，这时双向列表已经已经链接好了，但是题目里面唯一
 * 提供的一个引用还在链表尾部，所以再将该引用通过循环指向双向链表头部那个最小的节点并返回，OK，我的这种方法应该是比较好理解的。
 */
import java.util.LinkedList;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        //创建一个空队列
        LinkedList<TreeNode> queue=new LinkedList<TreeNode>();

        if(pRootOfTree==null) return null;
        else inRootTraverse(pRootOfTree, queue);

        while(queue.size()>1){
            pRootOfTree=queue.poll();//队首节点出队
            pRootOfTree.right=queue.peek();
            queue.peek().left=pRootOfTree;
        }
        //由于题目不让创建新的节点，而现在题目提供的引用指向列表尾部，所以只能将提供的引用指向链表首部
        while(pRootOfTree.left!=null) pRootOfTree=pRootOfTree.left;

        return pRootOfTree;
    }
    //中序遍历二叉搜索树
    public void inRootTraverse(TreeNode root,LinkedList<TreeNode> queue){
        if(root!=null){
            inRootTraverse(root.left, queue);
            queue.add(root);//入队
            inRootTraverse(root.right, queue);
        }
    }
}