Question 108
Convert an ordered array in ascending order into a highly balanced binary search tree. In this question, a highly balanced binary tree means that the absolute value of the height difference between the left and right subtrees of each node of a binary tree does not exceed 1. Example: Given an ordered array: [-10,-3,0,5,9], a possible answer is: [0,-3,9,-10,null,5], which can represent the following height Balanced binary search tree: 0 / -3 9 / / -10 5 Source: LeetCode Link: https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
Question-solving ideas
- From the definition, we know that the middle order traversal of BST is an increasing sequence, and the given array is actually middle order Traversing the result
- Take the middle value of the ordered array as the root, the left part as the left tree, and the right part as the right tree. This BST tree can be restored by looping iteratively to divide into two.
code implementation
1. two-part + recursive implementation
Every time the middle value of the array is taken as a binary search tree
//Division + recursion to achieve class Solution108_1 {public TreeNode sortedArrayToBST(int[] nums) {return convertToBST(nums, 0, nums.length) -1);} TreeNode convertToBST(int[] nums, int begin, int end) {if (begin> end) return null; //take the median value int mid = begin + (end-begin) / 2; TreeNode root = new TreeNode(nums[mid]); //Left leaf tree root.left = convertToBST(nums, begin, mid-1); //Right leaf tree root.right = convertToBST(nums, mid + 1, end); return root; }}
2. Utilize Stack, derecursive implementation
- Define a stack to store the left and right index values of the array to be processed
- Define another stack to store the tree Node, because the node is an iterative process of initializing first and then updating the value of the node. So you need to borrow the stack to build the node first and establish a good relationship.
//Non-recursive implementation class Solution108_2 {public TreeNode sortedArrayToBST(int[] nums) {if (nums == null || nums.length == 0) return null; Stack stack = new Stack(); //The maximum index value of the array is stacked stack.add(nums.length-1); //The minimum index value of the array is stacked stack.add(0); Stack tree = new Stack(); TreeNode root = new TreeNode(0); //Push new tree nodes into the stack tree.add(root); while (!stack.isEmpty()) {int left = stack.pop(); int right = stack.pop(); //Find the intermediate node index value int mid = left + (right-left) / 2; TreeNode node = tree.pop(); //Update the root Node value node.val = nums[mid]; //Calculate the maximum and minimum index values of the left leaf node int r = mid-1, l = left; //If there is a left leaf node if (l <= r) {node.left = new TreeNode(0); //Push new tree nodes into the stack tree.add(node.left); //Push the corresponding right index value into the stack stack.push(r); //The corresponding left index value is pushed into the stack stack.push(l);} //Calculate the maximum and minimum index value of the right node l = mid + 1; r = right; if (l <= r) {node.right = new TreeNode( 0); //Any new tree node is pushed into the stack tree.add(node.right); //The corresponding right index value is pushed into the stack stack.push(r); //The corresponding left index value is pushed into the stack stack.add(l) ;}} return root; }}
Summary
Unsurprisingly, by submitting the code, it is found that the stack implementation will be much slower than the recursive execution efficiency. This is because:
- Stack implementation requires frequent push (into the stack) and pop (out of the stack) operations, resulting in performance degradation
data
- Sample source code
- Original address
- Spring Boot, Spring Cloud sample learning