A C++ Solution And Its Formal Proof
Here is my solution. I think many people used the same solution, but have you considered how to prove it? Do you really understand why this algorithm never prod
Here is my solution. I think many people used the same solution, but have you considered how to prove it? Do you really understand why this algorithm never produces a node with two subtrees whose sizes differ by more than one? The algorithm is relatively simple and easy to understand, but I believe that the correctness of it is not obvious and we should try to understand the details.\n\n```\nclass Solution {\n    TreeNode* construct(vector<int>& nums, int begin, int end)\n    {\n        if (begin == end) {\n            return nullptr;\n        }\n        int mid = (begin + end) / 2;\n        auto root = new TreeNode(nums[mid]);\n        root->left = construct(nums, begin, mid);\n        root->right = construct(nums, mid + 1, end);\n        return root;\n    }\npublic:\n    TreeNode* sortedArrayToBST(vector<int>& nums) {\n        return construct(nums, 0, nums.size());\n    }\n};\n```\n\nDuring one recursion, if (end - begin) is an odd number, the left part and the right part will have the same number of elements. Since the same function is applied to the left part and the right part, it is obvious that the left tree and the right tree will have the same height. In fact, they will have exactly the same structure!\n\nBut, if (end - begin) is an even number, can this algorithm produce two subtrees with the same height? If we consider two arbitrary trees whose sizes differ by one, the heights of them may differ by more than one! So, how could we guarantee that this algorithm never produces this kind of results? Actually, each subtree will also be almost evenly divided, but this is still not a proof. Let me try to give a formal proof. The following proposition is what I want to prove.\n\nIf (end - begin) is an even number, this algorithm can still produce two subtrees whose sizes differ by at most one.\n\nProof:\n\n(1) If (end - begin) == 0, the problem is trivial, because we even don\'t have the root.\n(2) If (end - begin) == 2, the problem is trivial, because the size of the left subtree is zero and the size of the right subtree is one.\n(3) If (end - begin) >= 4, let N = (end - begin). We know that the size of the left subtree is N/2 - 1 and the size of the right subtree is N/2. Now we have two cases.\n(3.1) If N/2 - 1 is an even number, N/2 is odd. If we further divide the left subtree L and the right subtree R, we will have four subtrees LL, LR, RL, RR with sizes M - 1, M, M, M, where M = (N/2 - 1)/2. According to induction, we know that the heights of LL and LR differ by at most one. We also know that the heights of LR, RL, RR are equal. Thus, we know that the height of L and the height of R differ by at most one.\n(3.2) If N/2 - 1 is an odd number, N/2 is even. According to the induction hypothesis, the heights of RL and RR differ by at most one. We also know that the heights of LL, LR, RL are equal. Thus, we know that the heights of L and R differ by at most one.\n\nQ.E.D.
[]