题目描述

做的时候被递归的指针指来指去给绕晕了，想到既然是BST那么是不是代表可以用堆来解题。DFS遍历一遍树把节点全部塞入最小堆里，然后一个个取出来和前后节点连接指针就可以了。

时间复杂度

应该是O(nlogn)吧？DFS遍历一次树O(n)，加插入堆和遍历堆O(nlogn)。

Java 代码

class Solution {
        //使用最小堆来存储节点，根据节点的val值来排序
        PriorityQueue<TreeNode> minHeap = new PriorityQueue<>(new Comparator<TreeNode>() {
            @Override
            public int compare(TreeNode o1, TreeNode o2) {
                //1.最小堆就用o1减o2，最大堆就用o2减o1。或者说不论哪个容器只要在重写compare时，从小到大（最小堆）就用o1减o2，从大到小就用o2减o1
                return o1.val - o2.val;
            }
        });

        public TreeNode convert(TreeNode pRootOfTree) {
            if(pRootOfTree == null){
                return null;
            }
            dfs(pRootOfTree);
            TreeNode res = null;
            TreeNode pre = null;
            while(!minHeap.isEmpty()){
                TreeNode node = minHeap.remove();
                //第一个pop出最小堆的节点就是双向链表头
                //2.最左子节点也就是最小值的节点只需要赋值右节点
                if(res == null){
                    res = node;
                    //先要判断堆顶是否为null，有可能只有一个节点，如果堆顶不为null就将右指针指向堆顶
                    node.right = minHeap.isEmpty()?null:minHeap.peek();
                    pre = node;
                    continue;
                }
                //2.最右子节点，也就是最大值，只需要赋值左节点
                if(minHeap.isEmpty()){
                    node.left = pre;
                    continue;
                }
                //对于中间的节点，将它们的左指针设为pre，右指针设为堆顶的元素
                node.left = pre;
                node.right = minHeap.peek();
                //3.别忘了更新pre
                pre = node;
            }
            return res;
        }

        //将所有的节点放入最小堆
        public void dfs(TreeNode root){
            if(root == null){
                return;
            }
            minHeap.offer(root);
            dfs(root.left);
            dfs(root.right);
        }
    }