leetcode-Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. 문제를 푸는 방법도 귀속입니다. 체인 테이블의 중점을 뿌리 노드로 하고 왼쪽 요소를 뿌리 노드의 왼쪽 노드로 하고 오른쪽 요소를 체인 테이블의 오른쪽 노드로 하고 왼쪽 요소와 오른쪽 요소를 귀속합니다.
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        return sortedListToBST(head, NULL);
    }
private:
    TreeNode* sortedListToBST(ListNode *head, ListNode *tail) {
        if (head == tail)
            return NULL;
            
        if (head->next == tail)
            return new TreeNode(head->val);
            
        ListNode *p1, *p2;
        p1 = p2 = head;
        
        while (p2!=tail && p2->next!=tail) {    //p1 ,p2 2 , p1 
            p1 = p1->next;
            p2 = p2->next->next;
        }
        
        TreeNode *root = new TreeNode(p1->val);
        
        root->left = sortedListToBST(head, p1);
        root->right = sortedListToBST(p1->next, tail);
        
        return root;
    }
};

좋은 웹페이지 즐겨찾기