程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode筆記:Convert Sorted Array to Binary Search Tree

LeetCode筆記:Convert Sorted Array to Binary Search Tree

編輯:C++入門知識

LeetCode筆記:Convert Sorted Array to Binary Search Tree


一. 題目描述

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

二. 題目分析

將二叉查找樹進行中序遍歷,就可以得到一個升序排序的數組,因此,一個已經排序的數組可以看做一個中序遍歷得到的數組,要得到一個高度平衡的二叉查找樹,可以使得左右子樹的節點數盡可能相等。因此,可以采用二分法將數組分為兩個子數組,中間值作為父節點,左邊的子數組作為左子樹,右邊的子數組作為右子樹進行遞歸,這樣就可以得到一個高度平衡的二叉查找樹。

三. 示例代碼

#include 
#include 

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution
{
public:
    TreeNode* sortedArrayToBST(vector& nums)
    {
        return generateBST(0, num.size() - 1, num);
    }

private:
    TreeNode* generateBST(int left, int right, vector& num)  
    {  
        if (left > right)  
            return nullptr;  
        else if (left == right)  
            return new TreeNode(num[left]);  
        else  
        {  
            int mid = (left + right) / 2;  
            TreeNode* node = new TreeNode(num[mid]);  
            node->left = generateBST(left, mid - 1, num);  
            node->right = generateBST(mid + 1, right, num);  
            return node;  
        }  
    }  
};

四. 小結

這道題的技巧主要在於二叉查找樹的中序遍歷就是一個升序的數組,因此,本題就是根據一個二叉查找樹的中序構建一個二叉查找樹,由於要求高度平衡,因此,可以考慮左右兩個子樹的結點個數相同,這樣就可以得到唯一的一顆二叉查找樹。


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved