LeetCode - 將有序數組轉為二叉搜索樹

2020-09-11 吃泡菜的魚

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 everynode never differ by more than 1.

Example:

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

這道題是要將有序數組轉為二叉搜索樹，所謂二叉搜索樹，是一種始終滿足左<根<右的特性，如果將二叉搜索樹按中序遍歷的話，得到的就是一個一個有序數組。反之，我們可以得知，根節點應該是有序數組的中間點，從中間點分開為左右兩個有序數組，再分別找出其中間點的左右兩個子節點，這不就是二分查找法的核心思想麼。所以這道題考的就是二分查找法，代碼如下：

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

我們也可以不額外使用額外的遞歸函數，而是在原函數中完成遞歸，由於原函數的參數是一個數組，所以當把輸入數組的中間數字取出來後，需要把所有的兩端數組組成一個新的數組，並且分別調用遞歸函數，並且連到新創建的cur節點的左右字節點上，代碼如下：

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

相關焦點

  • leetcode樹之將有序數組轉換為二叉搜索樹
    序本文主要記錄一下leetcode樹之將有序數組轉換為二叉搜索樹題目將一個按照升序排列的有序數組，轉換為一棵高度平衡二叉搜索樹。示例:給定有序數組: [-10,-3,0,5,9],一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜索樹： 0 / \ -3 9 / / -10 5來源：力扣（LeetCode）連結：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
  • Leetcode每日一題108. 將有序數組轉換為二叉搜索樹
    什麼是二叉搜索樹二叉搜索樹（又稱二叉排序樹、二叉查找樹），是指一棵空樹或者具有下列性質的二叉樹：1 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；2 若任意節點的右子樹不空，則右子樹上所有節點的值均大於或等於它的根節點的值；3 任意節點的左、右子樹也分別為二叉查找樹；我們先觀察題目給的例子：根節點 0 的左邊所有數都
  • 網際網路公司高頻面試題目：如何把二叉搜索樹轉成累加樹
    538.把二叉搜索樹轉換為累加樹題目連結：https://leetcode-cn.com/problems/convert-bst-to-greater-tree/>給出二叉 搜索 樹的根節點，該樹的節點值各不相同，請你將其轉換為累加樹（Greater Sum Tree），使每個節點 node 的新值等於原樹中大於或等於 node.val 的值之和。
  • leetcode樹之二叉搜索樹的最近公共祖先
    序本文主要記錄一下leetcode樹之二叉搜索樹的最近公共祖先題目給定一個二叉搜索樹p、q 為不同節點且均存在於給定的二叉搜索樹中。注意：本題與主站 235 題相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/來源：力扣（LeetCode）連結：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof著作權歸領扣網絡所有
  • 樹、二叉樹、二叉搜索樹的實現和特性
    「有序樹」，反之稱為 「無序樹」。在有序樹中，一個結點最左邊的子樹稱為 「第一個孩子」，最右邊的稱為 「最後一個孩子」。本身是有序樹；樹中包含的各個結點的度不能超過2，即只能是0、1或者2.Binary Search Tree二叉搜索樹，也稱二叉搜索樹、有序二叉樹（Ordered Binary Tree）、排序二叉樹（Sorted Binary Tree），是指一顆空樹或者具有下列性質的二叉樹：
  • 二叉樹：二叉搜索樹登場
    給定二叉搜索樹（BST）的根節點和一個值。二叉搜索樹是一個有序樹：若它的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；若它的右子樹不空本題，其實就是在二叉搜索樹中搜索一個節點。那麼我們來看看應該如何遍歷。
  • 二叉搜索樹的第k大節點 - leetcode 劍指offer
    點 45 分準時更新公眾號 每日精選算法題, 大家記得關注哦~ 另外在公眾號裡回復 offer 就能看到劍指 offer 系列當前連載的所有文章了題目描述給定一棵二叉搜索樹，1 ≤ k ≤ 二叉搜索樹元素個數題目樣例示例輸入: root = [3,1,4,null,2],
  • 二叉搜索樹的構建
    1 二叉搜索樹BST二叉搜索樹(Binary Search Tree，簡寫BST)，又稱為二叉排序樹或二叉查找樹。其定義為：對於樹中的每個節點，其左子樹的所有節點值都小於該節點的值，其右子樹的所有節點值都大於該節點的值。二叉搜索樹的任意一個子樹也是二叉搜索樹。
  • 二叉樹：搜索樹的最小絕對差
    「注意是二叉搜索樹」，二叉搜索樹可是有序的。遇到在二叉搜索樹上求什麼最值啊，差值之類的，就把它想成在一個有序數組上求最值，求差值，這樣就簡單多了。遞歸那麼二叉搜索樹採用中序遍歷，其實就是一個有序數組。「在一個有序數組上求兩個數最小差值，這是不是就是一道送分題了。」最直觀的想法，就是把二叉搜索樹轉換成有序數組，然後遍歷一遍數組，就統計出來最小差值了。
  • 二叉樹：我是不是一棵二叉搜索樹
    遞歸法可以遞歸中序遍歷將二叉搜索樹轉變成一個數組，代碼如下：vector<int root) {    if (root == NULL) return;    traversal(root->left);    vec.push_back(root->val); // 將二叉搜索樹轉換為有序數組
  • 二叉搜索樹遞歸版c++
    2.二叉查找樹是基礎性數據結構，用於構建更為抽象的數據結構，如集合、多重集、關聯數組等。3.二叉查找樹的查找過程和次優二叉樹類似，通常採取二叉鍊表作為二叉查找樹的存儲結構。中序遍歷二叉查找樹可得到一個關鍵字的有序序列，一個無序序列可以透過建構一棵二叉查找樹變成一個有序序列，建構樹的過程即為對無序序列進行查找的過程。
  • leetcode173_go_二叉搜索樹迭代器
    題目實現一個二叉搜索樹迭代器。你將使用二叉搜索樹的根節點初始化迭代器。調用 next() 將返回二叉搜索樹中的下一個最小的數。iterator.next(); // 返回 15iterator.hasNext(); // 返回 trueiterator.next(); // 返回 20iterator.hasNext(); // 返回 false提示：next() 和 hasNext() 操作的時間複雜度是 O(1)，並使用 O(h) 內存，其中 h 是樹的高度
  • 二叉搜索樹迭代版c++
    二叉搜索樹（Binary Search Tree），也稱為二叉排序樹（Binary Sort tree），是指一棵空樹或者具有下列性質的二叉樹：若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；若任意節點的右子樹不空，則右子樹上所有節點的值均
  • 網際網路公司高頻面試題目：構造一棵二叉搜索樹
    108.將有序數組轉換為二叉搜索樹將一個按照升序排列的有序數組，轉換為一棵高度平衡二叉搜索樹。示例:108.將有序數組轉換為二叉搜索樹這和轉換為一棵普通二叉搜索樹有什麼差別呢？本題其實要比 和 簡單一些，因為有序數組構造二叉搜索樹，尋找分割點就比較容易了。分割點就是數組中間位置的節點。那麼為問題來了，如果數組長度為偶數，中間節點有兩個，取哪一個？取哪一個都可以，只不過構成了不同的平衡二叉搜索樹。
  • 使用快慢指針把有序鍊表轉換二叉搜索樹
    給定一個單鍊表，其中的元素按升序排序，將其轉換為高度平衡的二叉搜索樹。本題中，一個高度平衡二叉樹是指一個二叉樹每個節點的左右兩個子樹的高度差的絕對值不超過 1。總結做這道題我們首先要明白什麼是二叉搜索樹
  • 尋找Nemo的樂趣:什麼是二叉搜索樹?
    同理，二叉搜索樹通過在每一步都減少選項來幫助找到想要的東西。首先，二叉搜索樹到底是什麼?二叉搜索樹(BST)是一種特殊類型的樹形數據結構，由節點及其子節點組成，子節點也被視作「後代」，可以把它想像成一棵倒置的樹或者是樹的根部。每個節點最多只能有2個子節點：左節點和右節點。
  • 網際網路公司高頻面試題：二叉搜索樹中的插入操作
    701.二叉搜索樹中的插入操作連結：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/給定二叉搜索樹（BST）的根節點和要插入樹中的值，將值插入二叉搜索樹。
  • 二叉樹：求搜索樹中的眾數
    501.二叉搜索樹中的眾數給定一個有相同值的二叉搜索樹（BST），找出 BST 中的所有眾數（出現頻率最高的元素）。首先如果不是二叉搜索樹的話，應該怎麼解題，是二叉搜索樹，又應該如何解題，兩種方式做一個比較，可以加深大家對二叉樹的理解。
  • LeetCode題解 | 538. 把二叉搜索樹轉換為累加樹
    把二叉搜索樹轉換為累加樹（點擊查看題目）題目描述給定一個二叉搜索樹（Binary Search Tree），把它轉換成為累加樹（Greater Tree)，使得每個節點的值是原來的節點值加上所有大於它的節點值之和。
  • 什麼是二叉搜索樹，如何通過代碼實現它們？
    同理，二叉搜索樹通過在每一步都減少選項來幫助找到想要的東西。 首先，二叉搜索樹到底是什麼? 二叉搜索樹(BST)是一種特殊類型的樹形數據結構，由節點及其子節點組成，子節點也被視作「後代」，可以把它想像成一棵倒置的樹或者是樹的根部。