leetcode108

/**
 * 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 = 0;
            TreeNode root = null;
            while (Q.Count > 0 && 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 = 0; i < TreeList.Count; i++)
            {
                TreeList[i].val = nums[i];
            }

            return root;
        }
    }

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/#/description

补充一个python的实现，使用递归处理：

 1 class Solution:
 2     def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
 3         n = len(nums)
 4         if n == 0:#终止条件，返回空
 5             return None
 6         if n == 1:#终止条件，返回单节点
 7             return TreeNode(nums[0])
 8         mid = n // 2
 9         root = TreeNode(nums[mid])#将数组从中间一分为二
10         root.left = self.sortedArrayToBST(nums[:mid])#左子树
11         root.right = self.sortedArrayToBST(nums[mid+1:])#右子树
12         return root#返回