aboutsummaryrefslogtreecommitdiff
path: root/convert_sorted_bst.cpp
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /convert_sorted_bst.cpp
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'convert_sorted_bst.cpp')
-rw-r--r--convert_sorted_bst.cpp29
1 files changed, 29 insertions, 0 deletions
diff --git a/convert_sorted_bst.cpp b/convert_sorted_bst.cpp
new file mode 100644
index 0000000..8b5b656
--- /dev/null
+++ b/convert_sorted_bst.cpp
@@ -0,0 +1,29 @@
+// 109. Convert Sorted List to Binary Search Tree
+#include "leetcode.h"
+
+/*
+ * given 'head' of a singly linked list where elements are sorted in ascending
+ * order convert it to a height balanced binary search tree. meaning the depth
+ * of two sub- trees of every node never differs by more than one.
+ */
+
+class Solution {
+public:
+ TreeNode *sortedListToBST(ListNode *head) {
+ if (!head)
+ return NULL;
+ if (!head->next)
+ return new TreeNode(head->val);
+ auto slow = head, fast = head, pre = head;
+ while (fast && fast->next) {
+ pre = slow;
+ slow = slow->next;
+ fast = fast->next->next;
+ }
+ pre->next = 0;
+ TreeNode *root = new TreeNode(slow->val);
+ root->left = sortedListToBST(head);
+ root->right = sortedListToBST(slow->next);
+ return root;
+ }
+};