本文共 3248 字，大约阅读时间需要 10 分钟。

题目描述

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

/**public class TreeNode {    int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {        this.val = val;    }}*/import java.util.Stack;public class Solution {    public TreeNode Convert(TreeNode pRootOfTree) {        if(pRootOfTree==null){            return null;        }        Stack
   
     stack = new Stack
    
     ();        collection(stack,pRootOfTree);        TreeNode first,second;        first = stack.pop();        first.right = null;        while(!stack.empty()){            second = stack.pop();            first.left = second;            second.right = first;            first = second;        }        first.left=null;        return first;    }    public void collection(Stack
     
       stack,TreeNode pRootOfTree){        if(pRootOfTree.left!=null){            collection(stack,pRootOfTree.left);        }        stack.push(pRootOfTree);        if(pRootOfTree.right!=null){            collection(stack,pRootOfTree.right);        }    }}
     
    
   

下面代码时间复杂度比较高，过不去

import java.util.Stack;import java.util.Queue;import java.util.LinkedList;public class Solution {    public TreeNode Convert(TreeNode pRootOfTree) {        if(pRootOfTree==null){            return null;        }        Stack
   
     stack = new Stack
    
     ();        Queue
     
       queue = new LinkedList
      
       ();        while(pRootOfTree!=null||stack.isEmpty()){            while(pRootOfTree!=null){                stack.push(pRootOfTree);                pRootOfTree = pRootOfTree.left;             }            //TreeNode temp;            if(!stack.isEmpty()){                pRootOfTree = stack.pop();                queue.add(pRootOfTree);                pRootOfTree = pRootOfTree.right;            }        }        TreeNode first,second,head;        first = queue.poll();        head = first;        while(!queue.isEmpty()){            second = queue.poll();            first.left = second;            second.right = first;            first = second;        }        head.left=null;        return head;    }}
      
     
    
   

改了一下，下面可以通过了

import java.util.Stack;public class Solution {    public TreeNode Convert(TreeNode pRootOfTree) {        if(pRootOfTree==null){            return null;        }        else if(pRootOfTree.left==null&&pRootOfTree.right==null){            return pRootOfTree;        }        Stack
   
     stack = new Stack
    
     ();        TreeNode first=null,second=null,head=null;        while(pRootOfTree!=null||!stack.isEmpty()){            while(pRootOfTree!=null){                stack.push(pRootOfTree);                pRootOfTree = pRootOfTree.left;            }            //TreeNode temp;            if(!stack.isEmpty()){                pRootOfTree = stack.pop();                if(head==null){                    first = pRootOfTree;                    head = first;                }                else{                    second = pRootOfTree;                    first.right = second;                    second.left = first;                    first = second;                }                pRootOfTree = pRootOfTree.right;            }        }        second.right=null;        return head;    }}
    
   

转载地址：http://dyonn.baihongyu.com/