LeetCode --- 109. Convert Sorted List to Binary Search Tree

タイトルリンク: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.
この問題の要件は,秩序チェーンテーブルを高度にバランスのとれた二叉探索ツリー(BST)に変換することである.
1.sortedArrayToBST利用
まずチェーンテーブルを配列に変換し、Convert Sorted Array to Binary Search TreeのsortedArrayToBST関数を使用します.
配列が整列しているため,二叉探索ツリーの前順遍歴に相当する.また,二叉探索木の高さバランス,すなわち左右のサブツリーの高さの差が1以下であることが要求されるため,配列の中間の数をルートノードとし,左を左サブツリー,右を右サブツリーとして,高さバランスの二叉探索木を構築することができる.
このように,コンセプトはConstruct Binary Tree from Preorder and Inorder TraversalおよびConstruct Binary Tree from Inorder and Postorder Traversalとあまり差がなく,いずれも再帰構造左右のサブツリーでよい.
時間複雑度:O(n)
空間複雑度:O(n)

 1 class Solution 
 2 {
 3 public:
 4     TreeNode *sortedListToBST(ListNode *head) 
 5     {
 6         vector<int> vi;
 7         for(ListNode *p = head; p != NULL; p = p -> next)
 8             vi.push_back(p -> val);
 9         return sortedArrayToBST(vi, 0, vi.size() - 1);
10     }
11 private:
12     TreeNode *sortedArrayToBST(vector<int> &num, int l, int r)
13     {
14         if(l > r)
15             return NULL;
16         
17         int m = (l + r) / 2;
18         TreeNode *root = new TreeNode(num[m]);
19         root -> left = sortedArrayToBST(num, l, m - 1);
20         root -> right = sortedArrayToBST(num, m + 1, r);
21         return root;
22     }
23 };

2.再帰的直接転化
上はチェーンテーブルを配列に格納する必要があるため,O(n)を申請するスペースが必要であり,これはよくない.秩序チェーンテーブルを直接バランスのとれた二叉探索ツリーに変換することを考慮すべきである.Convert Sorted Array to Binary Search Treeと同様の考え方で,まず中間のノードをルートノードとして見つけ,次に左を左サブツリー,右を右サブツリーとし,左右のサブツリーを再帰的に構築すればよい.中間ノードをどのように見つけるかについては、ここでは、遅いポインタsを利用して、遅いポインタsが一歩歩くたびに、速いポインタfが2歩歩くたびに、fが最後のノードに達すると、sは中間ノードを指す.これにより、ルートノードが見つかり、左ノードをそれぞれ再帰して左サブツリーを生成し、右ノードを再帰して右サブツリーを生成します.
このように,コンセプトはConstruct Binary Tree from Preorder and Inorder TraversalおよびConstruct Binary Tree from Inorder and Postorder Traversalとあまり差がなく,いずれも再帰構造左右のサブツリーでよい.
時間複雑度:O(n)
空間複雑度:O(n)

 1 class Solution
 2 {
 3 public:
 4     TreeNode *sortedListToBST(ListNode *head)
 5     {
 6         if(head == NULL || head -> next == NULL)
 7             return head == NULL ? NULL : new TreeNode(head -> val);
 8         
 9         //       
10         ListNode *f = head -> next -> next, *s = head;
11         while(f != NULL && f -> next != NULL)
12         {
13             f = f -> next -> next;
14             s = s -> next;
15         }
16         
17         ListNode *l = head, *m = s -> next, *r = m -> next;
18         s -> next = NULL;
19         
20         TreeNode *root = new TreeNode(m -> val);
21         root -> left = sortedListToBST(l);
22         root -> right = sortedListToBST(r);
23         
24         return root;
25     }
26 };

上のコードは,左右の領域を区別する際に左の最後のノードをNULLに指向させることで,元のチェーンテーブルの構造を変更する.次に、tailタグを追加して、ツリー領域を構築する最後のノードの次の位置を指すことを考慮します.これにより、元のチェーンテーブル構造を変更せずにツリーを構築できます.

 1 class Solution
 2 {
 3 public:
 4     TreeNode *sortedListToBST(ListNode *head)
 5     {
 6         return sortedListToBST(head, NULL);
 7     }
 8 private:
 9     //     ， head       ，tail        next  
10     TreeNode *sortedListToBST(ListNode *head, ListNode *tail)
11     {
12         if(head == tail || head -> next == tail)
13             return head == tail ? NULL : new TreeNode(head -> val);
14         
15         //       
16         ListNode *f = head -> next -> next, *s = head;
17         while(f != tail && f -> next != tail)
18         {
19             f = f -> next -> next;
20             s = s -> next;
21         }
22         
23         ListNode *lh = head, *lt = s -> next, *m = lt, 
24                  *rh = m -> next, *rt = tail;
25         TreeNode *root = new TreeNode(m -> val);
26         root -> left = sortedListToBST(lh, lt);
27         root -> right = sortedListToBST(rh, rt);
28         return root;
29     }
30 };

転載は出典を説明してください:LeetCode---109.Convert Sorted List to Binary Search Tree