leetcode 108. Convert Sorted Array to Binary Search Tree 构建平衡二叉搜索树 + DFS深度优先遍历

刺骨的言语ヽ痛彻心扉 2022-06-08 04:11 169阅读 0赞

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

根据一个排序好的数组构建一个平衡的二叉搜索树。  
要和[中后序构造BST][BST]、[中前序构造BST][BST 1]一起学习。

代码如下：

/*class TreeNode 
    {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
    }*/
    
    /*
     * 构建一个有序数组构建一个平衡的二叉搜索树，
     * 
     * 平衡树的构建直接取中间部分就可以了
     * */
    public class Solution
    {
        public TreeNode sortedArrayToBST(int[] nums) 
        {
            if(nums == null)
                return null;
            return getBST(nums,0,nums.length-1);
        }
    
         TreeNode getBST(int[] nums, int beg, int end)
         {
            if(beg <= end)
            {
                int mid = (end-beg)/2 +beg;
                TreeNode root = new TreeNode(nums[mid]);
                root.left = getBST(nums, beg, mid-1);
                root.right = getBST(nums, mid+1, end);
                return root;
            }else
                return null;
        }
    }

下面是C++的做法，就是类似使用折半查找的思想去做

代码如下：

#include <iostream>
    #include <vector>
    #include <queue>
    #include <algorithm>
    
    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<int>& nums) 
        {
            if (nums.size() <= 0)
                return NULL;
            return getAll(nums, 0, nums.size() - 1);
        }
    
        TreeNode* getAll(vector<int> a, int beg, int end)
        {
            if (beg > end)
                return NULL;
            else
            {
                int mid = (end - beg) / 2 + beg;
                TreeNode* root = new TreeNode(a[mid]);
                root->left = getAll(a, beg, mid - 1);
                root->right = getAll(a, mid + 1, end);
                return root;
            }
        }
    };

[BST]: http://blog.csdn.net/jackzhang_123/article/details/77977904
[BST 1]: http://blog.csdn.net/jackzhang_123/article/details/77977697