《剑指Offer》36：二叉搜索树与双向链表

绝地灬酷狼 2022-12-08 14:25 192阅读 0赞

## 题目 ##

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

![2101c9e3cec72cd33f6923066d469317.png][]

二叉树节点的定义如下：

public static class TreeNode { 
    	public int val;
    	public TreeNode left;
    	public TreeNode right;
    	public TreeNode(int x) {  val = x; }
    }

## 分析 ##

众所周知，中序遍历二叉搜索树会得到有序的序列，我们目标是在**中序遍历二叉搜索树过程中，逐步将其转换成有序的双向链表**。另外，将树节点的左子树指针转换成双向链表节点的前驱指针，而树节点的右子树指针转换成双向链表节点的后驱指针。

![f034a36074afb5dcf22546407edddf73.png][]

## 放码 ##

import com.lun.util.BinaryTree.TreeNode;
    
    public class ConvertBSTToLinkedList { 
    
    	private TreeNode last;//用于指向双向链表的尾节点
    	
    	public TreeNode convert(TreeNode root) { 
    		convertNode(root);
    		
    		TreeNode head = last;
    		while(head != null && head.left != null) { 
    			head = head.left;
    		}
    		return head;
    	}
    
    	private void convertNode(TreeNode node) { 
    		
    		if(node == null) { 
    			return;
    		}
    		
    		TreeNode current = node;
    		
    		if(current.left != null) { 
    			convertNode(current.left);
    		}
    		
    		current.left = last;//1.执行到这步，左子树已经转换成有序双向链表
    		
    		if(last != null) { 
    			last.right = current;//2.
    		}
    		
    		last = current;//3.current转换成有序双向链表的新尾节点
    		
    		if(current.right != null) { 
    			convertNode(current.right);
    		}
    	}
    	
    }

## 测试 ##

import org.junit.Assert;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class ConvertBSTToLinkedListTest { 
    
    	@Test
    	public void test() { 
    		ConvertBSTToLinkedList cbl = new ConvertBSTToLinkedList();
    		TreeNode root = makeABST();
    		TreeNode head = cbl.convert(root);
    		Assert.assertEquals("4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16 -> \n" + 
    				"16 -> 14 -> 12 -> 10 -> 8 -> 6 -> 4 -> ", printList(head));
    	}
    	
    	private TreeNode makeABST() { 
    		int[] array = { 10, 6, 14, 4, 8, 12, 16};
    		return BinaryTree.integerArray2BinarySearchTree(array);
    	}
    	
    	private String printList(TreeNode head) { 
    		String result = "";
    		
    		TreeNode p = head;
    		
    		while(true) { 
    			result += (p.val + " -> ");
    			
    			if(p.right == null) { 
    				break;
    			}
    			p = p.right;
    		}
    
    		result += "\n";
    		
    		while(p != null) { 
    			result = result +  p.val + " -> ";
    			p = p.left;
    		}
    		return result;
    	}
    	
    }

[2101c9e3cec72cd33f6923066d469317.png]: /images/20221123/a7a60f19f3b44e1193a192ae483c2c52.png
[f034a36074afb5dcf22546407edddf73.png]: /images/20221123/b9163a11069349bf992f4f8c65624a3f.png