Created
November 27, 2021 08:53
-
-
Save haase1020/a7f8b86ef93ac28f7c1971bc7420a3fe to your computer and use it in GitHub Desktop.
recursive solution to leet code problem #108 convert a sorted array into a binary search tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//Definition for a binary tree node; needs to be called with "new" | |
function TreeNode(val) { | |
this.val = val; | |
this.right = null; | |
this.left = null; | |
} | |
var sortedArrayToBST = function(nums) { | |
// base cases | |
if (nums.length === 1) return new TreeNode(nums[0]) | |
if (nums.length === 0) return null; | |
// create a new TreeNode (center) | |
let centerIndex = Math.floor(nums.length/2); | |
let root = new TreeNode(nums[centerIndex]); | |
// set the left node to center of left subtree | |
let leftSubtree = nums.slice(0,centerIndex); | |
root.left = sortedArrayToBST(leftSubtree); | |
//set the right node to center of the right subtree | |
let rightSubtree = nums.slice(centerIndex +1, nums.length); | |
root.right = sortedArrayToBST(rightSubtree); | |
return root; | |
}; | |
// test your work! | |
sortedArrayToBST([-10,-3,0,5,9]); // +. a root node representing this tree will look like: [0,03,9,-10,null,5] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment