博客

更多LeetCode算法与参考：

https://github.com/kkman2008/Notebook/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3.md

————————-

【题目】

对二叉树的节点来书，有本身的值域，有指向左孩子和右孩子的指针；对双链表的节点来说，有本身的值域，有指向上一个节点和下一个节点的指针。在结构上，两种结构有

相似性，现在有一棵搜索二叉树，请将其转换为一个有序的双向链表。

【解答思路1】

使用辅助队列，先遍历二叉搜索树，将节点存入一个队列，再依次出队中元素，将先后出队的节点前后链接起来。时间复杂度为O(N),空间复杂度为O(N)

【解答思路2】

使用递归，直接在二叉搜索树上修改指针，不需要使用辅助队列，时间复杂度是O(n),空间复杂度是树的高度；

public class TreeNode {
    public int val;
    public TreeNode left = null;
    public TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
  }
  
  // 二叉搜索树转换成双向链表--用递归
    public static TreeNode biSearchTreeToBidirectionlinkList(TreeNode head){
        if(head == null)
            return null;
        TreeNode tail = bstTolist(head);
        head = tail.right;
        tail.right = null;
        return head;
    }

    // 二叉搜索树转换成双向链表的递归函数
    public static TreeNode bstTolist(TreeNode head){
        if(head == null)
            return null;

        TreeNode leftE = bstTolist(head.left);
        TreeNode rightE = bstTolist(head.right);
        TreeNode leftS = leftE.right;
        TreeNode rightS = rightE.right;

        if(leftE!=null && rightE!=null){
            leftE.right = head;
            head.left = leftE;
            rightS.left = head;
            head.right = rightS;
            rightE.right = leftS;
            return rightE;
        }
        else if(leftE != null){
            leftE.right = head;
            head.left = leftE;
            head.right = leftS;
            return head;
        }
        else if(rightE != null){
            rightS.left = head;
            head.right = rightS;
            rightE.right = leftS;
            return rightE;
        }
        else{
            head.right = head;
            return head;
        }
    }