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

题目描述

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

/**public class TreeNode {    int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {        this.val = val;    }} */import java.util.*;public class Solution {    /*    方法一：非递归版解题思路：1.核心是中序遍历的非递归算法。2.修改当前遍历节点与前一遍历节点的指针指向。    * */    public TreeNode Convert1(TreeNode pRootOfTree) {        if(pRootOfTree==null)            return null;        if(pRootOfTree.left==null&&pRootOfTree.right==null){            return pRootOfTree;        }        Stack
   
     stack=new Stack<>();        TreeNode p=pRootOfTree;        boolean isFirst=true;        TreeNode pre=null;        while (!stack.isEmpty()||p!=null){            while (p!=null){                stack.push(p);                p=p.left;            }            p=stack.pop();            if(isFirst){                //用pRootOfTree记录返回值                pRootOfTree=p;                pre=p;                isFirst=false;            }else{                pre.right=p;                p.left=pre;                pre=p;            }            p=p.right;        }        return pRootOfTree;    }    /*方法二：递归版解题思路：1.将左子树构造成双链表，并返回链表头节点。2.定位至左子树双链表最后一个节点。3.如果左子树链表不为空的话，将当前root追加到左子树链表。4.将右子树构造成双链表，并返回链表头节点。5.如果右子树链表不为空的话，将该链表追加到root节点之后。6.根据左子树链表是否为空确定返回的节点。    * */    public TreeNode Convert(TreeNode pRootOfTree) {        if (pRootOfTree == null)            return pRootOfTree;        if (pRootOfTree.left == null && pRootOfTree.right == null) {            return pRootOfTree;        }        // 1.将左子树构造成双链表，并返回链表头节点        TreeNode left = Convert(pRootOfTree.left);        TreeNode p = left;        // 2.定位至左子树双链表最后一个节点        while (p!=null&&p.right!=null){            p=p.right;        }        // 3.如果左子树链表不为空的话，将当前root追加到左子树链表        if (left != null) {            p.right = pRootOfTree;            pRootOfTree.left = p;        }        // 4.将右子树构造成双链表，并返回链表头节点        TreeNode right = Convert(pRootOfTree.right);        // 5.如果右子树链表不为空的话，将该链表追加到root节点之后        if (right != null) {            right.left = pRootOfTree;            pRootOfTree.right = right;        }        return left == null ? pRootOfTree : left;    }    /*    * 方法三：改进递归版解题思路：思路与方法二中的递归版一致，仅对第2点中的定位作了修改，新增一个全局变量记录左子树的最后一个节点。    */    // 记录子树链表的最后一个节点，终结点只可能为只含左子树的非叶节点与叶节点    TreeNode leftLast = null;    public TreeNode Convert3(TreeNode pRootOfTree) {        if (pRootOfTree == null)            return pRootOfTree;        if (pRootOfTree.left == null && pRootOfTree.right == null) {            // 最后的一个节点可能为最右侧的叶节点            leftLast = pRootOfTree;            return pRootOfTree;        }        // 1.将左子树构造成双链表，并返回链表头节点        TreeNode left = Convert3(pRootOfTree.left);        // 3.如果左子树链表不为空的话，将当前root追加到左子树链表        if (left != null) {            leftLast.right = pRootOfTree;            pRootOfTree.left = leftLast;        }        // 当根节点只含左子树时，则该根节点为最后一个节点        leftLast = pRootOfTree;        // 4.将右子树构造成双链表，并返回链表头节点        TreeNode right = Convert3(pRootOfTree.right);        // 5.如果右子树链表不为空的话，将该链表追加到root节点之后        if (right != null) {            right.left = pRootOfTree;            pRootOfTree.right = right;        }        return left == null ? pRootOfTree : left;    }        /*    思路：因为是二叉搜索树，所以其中序遍历就是排好序的，利用这个排好序的List，为每一个节点的前后节点赋值。 注意：给每个节点的前后节点时，要注意中序遍历list的长度，避免数组出界    */    public TreeNode Convert4(TreeNode pRootOfTree) {        if(pRootOfTree!=null){            inOrder(pRootOfTree);            if(arr.size()>2){//注意数组出界问题                arr.get(0).right=arr.get(1);                arr.get(arr.size()-1).left=arr.get(arr.size()-2);            }            if(arr.size()>3){//注意数组出界问题，极端树，5->4->3->2->1，这样情况下画一画                for (int i=1;i
    
      arr=new ArrayList<>();    private void inOrder(TreeNode root){        if(root!=null){            inOrder(root.left);            arr.add(root);            inOrder(root.right);        }    }}
    
   

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