leetcode 109. Convert Sorted List to Binary Search Tree 链表构造平衡二叉搜索树 + DFS

「爱情、让人受尽委屈。」 2022-06-08 04:12 208阅读 0赞

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

根据一个排序好的链表构造二叉平衡树，这个问题的重点是找到中间元素，使用双指针即可。

建议和[ leetcode 108. Convert Sorted Array to Binary Search Tree 构建平衡二叉搜索树 + DFS][leetcode 108. Convert Sorted Array to Binary Search Tree _ _ DFS]、[leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal 中后序构造BST][leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal _BST]、[ leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal 中前序构造BST][leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal _BST]放到一起学习。

代码如下：

/*class ListNode 
    {
         int val;
         ListNode next;
         ListNode(int x) { val = x; }
    }
    class TreeNode
    {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
    }*/
    
    /*
     * 这个题很简单，主要就是使用数组类似的方法去做
     * 问题的关键就是找到middle位置，可以考虑使用双指针来解决
     * */
    public class Solution 
    {
        public TreeNode sortedListToBST(ListNode head) 
        {
            return toBST(head,null);
        }
    
        public TreeNode toBST(ListNode head, ListNode tail)
        {
            if(head == tail)
                return null;
            else
            {
                ListNode mid = getMid(head,tail);
                TreeNode root = new TreeNode(mid.val);
                //注意这个要考虑到head和tail
                root.left = toBST(head, mid);
                root.right = toBST(mid.next,tail);
                return root;
            }
        }
    
        //双指针遍历
        public ListNode getMid(ListNode head,ListNode tail)
        {
            ListNode slow = head,fast = head;
            while(fast!=tail)
            {
                fast = fast.next;
                if(fast!=tail)
                {
                    fast = fast.next;
                    slow = slow.next;
                }
            }
            return slow;
        }
    }

下面是C++的做法，和上一道题一模一样，直接类似二叉树DFS深度优先遍历即可，不过这里用到了双指针来寻找中间节点

代码如下：

#include <iostream>
    #include <vector>
    #include <queue>
    #include <algorithm>
    
    using namespace std;
    /*
    struct ListNode 
    {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        TreeNode* sortedListToBST(ListNode* head)
        {
            return getAll(head,NULL);
        }
    
        TreeNode* getAll(ListNode* beg , ListNode* end)
        {
            if (beg == end)
                return NULL;
            else
            {
                ListNode* mid = getMid(beg,end);
                TreeNode* root = new TreeNode(mid->val);
                root->left = getAll(beg, mid);
                root->right = getAll(mid->next, end);
                return root;
            }
        }
    
        ListNode* getMid(ListNode* head, ListNode* end)
        {
            ListNode* fast = head;
            ListNode* slow = head;
            while (fast != end)
            {
                fast = fast->next;
                if (fast != end)
                {
                    fast = fast->next;
                    slow = slow->next;
                }
            }
            return slow;
        }
    };

[leetcode 108. Convert Sorted Array to Binary Search Tree _ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/77978036
[leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal _BST]: http://blog.csdn.net/jackzhang_123/article/details/77977904
[leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal _BST]: http://blog.csdn.net/jackzhang_123/article/details/77977697