/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution
{
//private TreeNode Insert(TreeNode T, int x)
//{
// if (T == null)
// {
// T = new TreeNode(x);
// return T;
// }
// else if (x < T.val)
// {
// T.left = Insert(T.left, x);
// }
// else if (x > T.val)
// {
// T.right = Insert(T.right, x);
// }
// return T;
//} Queue<TreeNode> Q = new Queue<TreeNode>(); List<TreeNode> TreeList = new List<TreeNode>(); void InOrder(TreeNode node)
{
if (node != null)
{
if (node.left != null)
{
InOrder(node.left);
} //中序处理
TreeList.Add(node); if (node.right != null)
{
InOrder(node.right);
}
}
} TreeNode BFS(int count)
{
int index = ;
TreeNode root = null;
while (Q.Count > && index < count)
{
var n = Q.Dequeue();
if (n == null)
{
index++;
n = new TreeNode(index);
root = n;
Q.Enqueue(n);
}
else
{
if (n.left == null && index < count)
{
index++;
n.left = new TreeNode(index); Q.Enqueue(n.left);
}
if (n.right == null && index < count)
{
index++;
n.right = new TreeNode(index);
Q.Enqueue(n.right);
}
}
}
return root;
} public TreeNode SortedArrayToBST(int[] nums)
{
var count = nums.Length;
Q.Enqueue(null);
var root = BFS(count); InOrder(root); for (int i = ; i < TreeList.Count; i++)
{
TreeList[i].val = nums[i];
} return root;
}
}
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/#/description
补充一个python的实现，使用递归处理：
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
n = len(nums)
if n == :#终止条件，返回空
return None
if n == :#终止条件，返回单节点
return TreeNode(nums[])
mid = n //
root = TreeNode(nums[mid])#将数组从中间一分为二
root.left = self.sortedArrayToBST(nums[:mid])#左子树
root.right = self.sortedArrayToBST(nums[mid+:])#右子树
return root#返回