先序遍历。
注意一点即可,在求中点的过程中,理论上left + (right-left) / 2
和left + (right - left + 1) / 2
都是合法的,但从题目中的示例可以得知,我们的代码里应使用后者才能符合题意。
这有一个小插曲,刚开始我在sortedArrayToBST
中写了如下代码,结果有5%的案例出现段错误,百思不得其姐,大家猜猜问题出在哪里?
TreeNode* sortedArrayToBST(vector<int>& num) { TreeNode *root; if (num.size() < 1) return root; root = preOrder(num, 0, num.size() - 1); return root; }
完整正确代码如下:
class Solution { public: /** * * @param num int整型vector * @return TreeNode类 */ TreeNode *sortedArrayToBST(vector<int> &num) { if (num.size() < 1) return nullptr; TreeNode *root = preOrder(num, 0, num.size() - 1); return root; } TreeNode *preOrder(vector<int> &num, int left, int right) { if (left > right) return nullptr; // 1. 找到中间节点 int mid = left + (right - left + 1) / 2; // 2. 递归构建左右 TreeNode *root = new TreeNode(num[mid]); root->left = preOrder(num, left, mid - 1); root->right = preOrder(num, mid + 1, right); return root; } };