目录

LeetCode-109.-有序链表转换二叉搜索树

JAY.LIN 收录于 Leetcode

2024-04-25 约 337 字预计阅读 1 分钟

https://bing.ee123.net/img/rand?artid=125122305

目录

LeetCode 109. 有序链表转换二叉搜索树

【存节点值】还是用老方法把节点的值都存下来然后递归构造

class Solution {

    List<Integer> list = new ArrayList();

    TreeNode dfs(int left, int right){
        if(left > right) return null;
        if(left == right) return new TreeNode(list.get(left));
        int mid = (left + right) >>> 1;
        return new TreeNode(list.get(mid), dfs(left, mid - 1), dfs(mid + 1, right));
    }

    public TreeNode sortedListToBST(ListNode head) {
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        return dfs(0, list.size() - 1);
    }
}

插句题外话，这样其实相当于后序遍历进行构造了，因为我们发现其实是先构造左侧后构造右侧，最后再构造根，再返回。但是很明显有序链表相当于BST的中序遍历，所以直接中序遍历就可以不用去get特定位置的值了。

【根据中序遍历】

具体方法还是需要先求出list的长度来，这个长度是用来决定二叉树dfs的深度的。

class Solution {

    ListNode node;

    public TreeNode dfs(int left, int right){
        if(left > right) return null;
        int mid = (left + right) >>> 1;
        TreeNode l = dfs(left, mid - 1);
        TreeNode root = new TreeNode();
        root.val = node.val;
        node = node.next;
        root.left = l;
        TreeNode r = dfs(mid + 1, right);
        root.right = r;
        return root;
    }

    public TreeNode sortedListToBST(ListNode head) {
        node = head;
        int n = 0;
        while(head != null){
            n++;
            head = head.next;
        }
        return dfs(0, n - 1);
    }
}