V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Acceml
V2EX  ›  程序员

[Leetcode] 109.有序链表转换二叉搜索树

  •  
  •   Acceml ·
    Acceml · 2019-03-17 20:54:31 +08:00 · 1290 次点击
    这是一个创建于 1837 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

    给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

    本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

    示例:

    给定的有序链表: [-10, -3, 0, 5, 9],

    一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:

          0
         / \
       -3   9
       /   /
     -10  5
    

    题解

    这道题和上一道类似,改动是把数组改成了链表。 链表求中间节点的经典方法是快慢指针,慢指针每次走一步,快指针每次都走两步,这样快指针走到链表结尾的时候,慢指针就指向中间节点。 这样就可以把问题转化为递归的子问题进行求解。

    class Solution {
        public TreeNode sortedListToBST(ListNode head) {
            if (head == null) {
                return null;
            }
            return helper(head, null);
        }
    
        public TreeNode helper(ListNode head, ListNode tail) {
            if (head == null || head == tail) {
                return null;
            }
            
            ListNode slow = head;
            ListNode fast = head;
            
            while (fast.next != tail && fast.next.next != tail) {
                fast = fast.next.next;
                slow = slow.next;
            }
    
            TreeNode current = new TreeNode(slow.val);
            current.left = helper(head, slow);
            current.right = helper(slow.next, tail);
            return current;
        } 
    }
    

    这道题目还有一个比较巧妙的办法是利用 BST 中序遍历是升序的性质,去求解,具体看代码注释。

    class Solution {
        private ListNode node;
    
        public TreeNode sortedListToBST(ListNode head) {
            if (head == null) {
                return null;
            }
    
            int size = 0;
            ListNode runner = head;
            node = head;
    
            while (runner != null) {
                runner = runner.next;
                size++;
            }
            // 先计算有几个节点
            return inorderHelper(0, size - 1);
        }
    
        public TreeNode inorderHelper(int start, int end) {
            if (start > end) {
                return null;
            }
            // 划分左右子树
            int mid = start + (end - start) / 2;
            TreeNode left = inorderHelper(start, mid - 1);
            // 中序遍历
            TreeNode treenode = new TreeNode(node.val);
            treenode.left = left;
            node = node.next;
    
            TreeNode right = inorderHelper(mid + 1, end);
            treenode.right = right;
    
            return treenode;
        }
    }
    

    最关键的一个步骤是node = node.next 这步的意思是基于: 在 BST 中任意子树,它的中序遍历的结果如果存在一个链表中,一定是一个升序的,可以一一对应上,所以中序遍历完(这里是构建完)一个节点链表+1。

    热门阅读

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5511 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 09:05 · PVG 17:05 · LAX 02:05 · JFK 05:05
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.