[leetcode]Convert Sorted List to Binary Search Tree

この問題はちょっと難しいです.△まず、この問題は新しいBSTを再作成することなので、元のリストでポインタを逆さまにする方法を考えなくてもいいです.1.まずこの問題はO(n*logn)なら簡単です.O(n)空間ができれば配列に変換すればO(n)時間は可能ですが、これは面白くありません.だから答えはO(1)空間,O(n)時間でよい.2.答えを見て、底から上へ考えていることを知った.しかし試してみると、生成されたサブツリーのノード数はまず少なくなり、それから多くなり、それから少なくなり(最初は1ノードの左サブツリー、それから3ノードのサブツリーを生成するときは、また1ノードの右サブツリーを生成する)、ループで書くと状態がよく表示されず、スタックで多くのことを覚える必要がある.3.似たような手順をたくさん見て、再帰でやることができますが、これは底から上への再帰です.どうすればいいですか.答えを見てみると、こんな法則があることに気づいた.再帰的に伝達されるのは同じチェーンテーブルであるが、このチェーンテーブルのノードは絶えず前進している.本当に決定的な変化は区間です5.再帰呼び出しが開始されるたびに、ノードポインタは区間の1番目を指し、終了時にノードのポインタは区間の末尾の1番目を指すことがわかる.これは,一つのノードが成立し,k級が成立したときにk+1級も成立したため,数学的帰納法により証明できる.6.再帰呼び出しのたびに、左右の2つの部分に分かれ、左の構造が完了すると、ちょうどmidを指し、rootを作成し、右の部分のサブツリーを構築し続けます.Javaで書こうと思っていたのですが、ポインタのポインタJavaが書きにくいことに気づきました.やはりC++でしょう.ポインタや木ですね.C++がいいです.

class Solution {

public:

    TreeNode *sortedListToBST(ListNode *head) {

        int len = 0;

        ListNode * node = head;

        while (node != NULL)

        {

            node = node->next;

            len++;

        }

        return buildTree(head, 0, len-1);

    }

    

    TreeNode *buildTree(ListNode *&node, int start, int end)

    {

        if (start > end) return NULL;

        int mid = start + (end - start) / 2;

        TreeNode *left = buildTree(node, start, mid-1);

        TreeNode *root = new TreeNode(node->val);

        root->left = left;

        node = node->next;

        root->right = buildTree(node, mid+1, end);

        return root;

    }

};