剑指offer（第二版）面试题36：二叉搜索树与双向链表（Java）

比眉伴天荒 2021-11-11 09:36 226阅读 0赞

### 题目 ###

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

### 解题思路 ###

利用分治策略，将排序二叉树分为左子树和右子树两个部分，其中左子树的最后一个节点为根节点的前一节点，右子树的第一个节点为根节点的后一个节点，二叉排序树中分为左节点和右节点，可以利用左节点存储前节点，右节点存储后节点，利用迭代计算的方式得到双向链表。

![20190805153853988.png][]

代码如下：

import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    public class test {
    
    	
    	public static void main(String[] args) {
    		BNode node1 = new BNode(10);
    		BNode node2 = new BNode(5);
    		BNode node3 = new BNode(12);
    		BNode node4 = new BNode(4);
    		BNode node5 = new BNode(7);
    		node1.left=node2;
    		node1.right=node3;
    		node2.left=node4;
    		node2.right=node5;
    		BNode n = covert(node1);
    		while(n!=null) {
    			System.out.print(n.data+"  ");
    			n = n.right;
    		}
    		
    	}
    
    	public static BNode covert(BNode n){
    		if(n==null)
    			return null;
    		if(n.right==null&&n.left==null){
    			return n;
    		}
    		BNode left = covert(n.left);
    		BNode p = left;
    		if(left!=null) {
    			while(p!=null&&p.right!=null) {
    				p = p.right;
    			}
    			p.right = n;
    			n.left = p;
    		}
    		BNode right = covert(n.right);
    		if(right!=null) {
    			right.left = n;
    			n.right = right;
    		}
    		return left;
    	}
    	
    	public static class BNode{
    		public BNode left;
    		public BNode right;
    		public int data;
    		
    		BNode(int data){
    			this.left = null;
    			this.right = null;
    			this.data = data;
    		}
    		
    		
     
    	}
    	
    }

[20190805153853988.png]: /images/20211109/45f2658129b840e8a9ba9ee7e4f6effb.png