[LeetCode] 108. Convert Sorted Array to Binary Search Tree

发布时间：2020-12-14 03:46:04 所属栏目：大数据来源：网络整理

导读：Given an array where elements are sorted in ascending order,convert it to a height balanced BST. For this problem,a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of? every ?node never differ

Given an array where elements are sorted in ascending order,convert it to a height balanced BST.

For this problem,a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of?every?node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,5,9],One possible answer is: [0,9,-10,null,5],which represents the following height balanced BST:

      0
     /    -3   9
   /   /
 -10  5?

给定一个升序排序的数组，把它转成一个高度平衡的二叉搜索树(两个子树的深度相差不大于1)。

二叉搜索树的特点：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
4. 没有键值相等的节点。

中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉查找树变成一个有序序列，构造树的过程即为对无序序列进行查找的过程。

反过来，根节点就是有序数组的中间点，从中间点分开为左右两个有序数组，再分别找出两个数组的中间点作为左右两个子节点，就是二分查找法。

解法1：二分法BS + 递归Recursive

解法2: 二分法 + 迭代

Java: Recursive

public TreeNode sortedArrayToBST(int[] num) {
    if (num.length == 0) {
        return null;
    }
    TreeNode head = helper(num,num.length - 1);
    return head;
}

public TreeNode helper(int[] num,int low,int high) {
    if (low > high) { // Done
        return null;
    }
    int mid = (low + high) / 2;
    TreeNode node = new TreeNode(num[mid]);
    node.left = helper(num,low,mid - 1);
    node.right = helper(num,mid + 1,high);
    return node;
}

Java: Iterative　　

public class Solution {
    
    public TreeNode sortedArrayToBST(int[] nums) {
        
        int len = nums.length;
        if ( len == 0 ) { return null; }
        
        // 0 as a placeholder
        TreeNode head = new TreeNode(0); 
        
        Deque<TreeNode> nodeStack       = new LinkedList<TreeNode>() {{ push(head);  }};
        Deque<Integer>  leftIndexStack  = new LinkedList<Integer>()  {{ push(0);     }};
        Deque<Integer>  rightIndexStack = new LinkedList<Integer>()  {{ push(len-1); }};
        
        while ( !nodeStack.isEmpty() ) {
            TreeNode currNode = nodeStack.pop();
            int left  = leftIndexStack.pop();
            int right = rightIndexStack.pop();
            int mid   = left + (right-left)/2; // avoid overflow
            currNode.val = nums[mid];
            if ( left <= mid-1 ) {
                currNode.left = new TreeNode(0);  
                nodeStack.push(currNode.left);
                leftIndexStack.push(left);
                rightIndexStack.push(mid-1);
            }
            if ( mid+1 <= right ) {
                currNode.right = new TreeNode(0);
                nodeStack.push(currNode.right);
                leftIndexStack.push(mid+1);
                rightIndexStack.push(right);
            }
        }
        return head;
    }

}

Python:

class Solution(object):
    def sortedArrayToBST(self,nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        return self.sortedArrayToBSTRecu(nums,len(nums))

    def sortedArrayToBSTRecu(self,nums,start,end):
        if start == end:
            return None
        mid = start + self.perfect_tree_pivot(end - start)
        node = TreeNode(nums[mid])
        node.left = self.sortedArrayToBSTRecu(nums,mid)
        node.right = self.sortedArrayToBSTRecu(nums,end)
        return node

    def perfect_tree_pivot(self,n):
        """
        Find the point to partition n keys for a perfect binary search tree
        """
        x = 1
        # find a power of 2 <= n//2
        # while x <= n//2:  # this loop could probably be written more elegantly :)
        #     x *= 2
        x = 1 << (n.bit_length() - 1)  # use the left bit shift,same as multiplying x by 2**n-1

        if x // 2 - 1 <= (n - x):
            return x - 1  # case 1: the left subtree of the root is perfect and the right subtree has less nodes
        else:
            return n - x // 2  # case 2 == n - (x//2 - 1) - 1 : the left subtree of the root
                               # has more nodes and the right subtree is perfect.

C++:

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedArrayToBSTHelper(nums,nums.size() - 1);
    }

private:
    TreeNode *sortedArrayToBSTHelper(vector<int> &nums,int start,int end) {
        if (start <= end) {
            TreeNode *node = new TreeNode(nums[start + (end - start) / 2]);
            node->left = sortedArrayToBSTHelper(nums,start + (end - start) / 2 - 1);
            node->right = sortedArrayToBSTHelper(nums,start + (end - start) / 2 + 1,end);
            return node;
        }
        return nullptr;
    }
};

C++:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x),left(NULL),right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &num) {
        return sortedArrayToBST(num,num.size() - 1);
    }
    TreeNode *sortedArrayToBST(vector<int> &num,int left,int right) {
        if (left > right) return NULL;
        int mid = (left + right) / 2;
        TreeNode *cur = new TreeNode(num[mid]);
        cur->left = sortedArrayToBST(num,left,mid - 1);
        cur->right = sortedArrayToBST(num,right);
        return cur;
    }
};

类似题目：

[LeetCode] 109.?Convert Sorted List to Binary Search Tree 把有序链表转成二叉搜索树

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!