109.秩序チェーンテーブル変換二叉探索ツリー(java)
1100 ワード
package LeetCode;
import java.util.ArrayList;
import java.util.List;
/*
, , 。
, 1。
:
: [-10, -3, 0, 5, 9],
:[0, -3, 9, -10, null, 5], :
0
/ \
-3 9
/ /
-10 5
*/
public class SortedListToBST {
public TreeNode sortedListToBST(ListNode head) {
List listNode = new ArrayList<>();
ListNode node = head;
while (node != null) {
listNode.add(node.val);
node = node.next;
}
int left = 0;
int right = listNode.size() - 1;
return build(left, right, listNode);
}
public TreeNode build(int left, int right, List listNode) {
if (left > right) return null;
int mid = (left + right) / 2;
TreeNode treenode = new TreeNode(listNode.get(mid));
treenode.left = build(left, mid - 1, listNode);
treenode.right = build(mid + 1, right, listNode);
return treenode;
}
}