LeetCode C++ 108. Convert Sorted Array to Binary Search Tree【Tree】シンプル

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 every node 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

タイトル:昇順秩序配列を高さバランスツリーに変換します.
考え方1:以前にやった問題で,そのときの第一反応はこれらの値をAVLツリーに挿入することであった.次のコードがあります.

//    
void L(TreeNode *&root) {  
    TreeNode *temp = root;
    root = root->right;
    temp->right = root->left;
    root->left = temp;
}
//    
void R(TreeNode *&root) { 
    TreeNode *temp = root;
    root = root->left;
    temp->left = root->right;
    root->right = temp;
}

次に、下から上へ遡ると、高さとバランス係数を再帰的に求める関数です.

int getHeight(TreeNode *root) {
    if (!root) return 0;  
    return max(getHeight(root->left), getHeight(root->right)) + 1; 
}
int getFactor(TreeNode *root) {
    return getHeight(root->left) - getHeight(root->right);
}

次に、AVLツリーに挿入される関数です.

void insert(TreeNode *&root, int x) {
    if (!root) root = new TreeNode(x);  
    else {
        if (x < root->val) insert(root->left, x);
        else if (x > root->val) insert(root->right, x);
        else return;

        int fac1 = getFactor(root);
        if (fac1 >= 2) { 						//L
            int fac2 = getFactor(root->left);
            if (fac2 == 1) R(root);				//LL
            else if (fac2 == -1) {				//LR
                L(root->left);
                R(root);
            }
        } else if (fac1 <= -2) {				//R
            int fac3 = getFactor(root->right);
            if (fac3 == 1) {					//RL
                R(root->right);
                L(root);
            }
            else if (fac3 == -1) L(root);		//RR
        }
    }
}

Update:AVLツリーの挿入関数を更新し、実際に高度な情報を格納しない前提で、効率を少し高めました.テーマとはあまり関係ありませんが:

void insert(TreeNode *&root, int x) {
   if (!root) root = new TreeNode(x);  
   else {
       if (x < root->val) insert(root->left, x);
       else if (x > root->val) insert(root->right, x);
       else return;

       int fac1 = getFactor(root);
       if (fac1 >= 2) { 
           if (x < root->left->val) R(root);
           else {
               L(root->left);
               R(root);
           }
       } else if (fac1 <= -2) {
           if (root->right->val < x) L(root);
           else {
               R(root->right);
               L(root);
           }
       }
   }
}

最後に、テーマが与える関数です.

/**
 * Definition for a binary tree node.
 * 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) {
        TreeNode *root = NULL;
        for (int i = 0; i < nums.size(); ++i) 
            insert(root, nums[i]); 
        return root;
    }
};

結果は過ぎて、emmm・・・時間はかかりますが:

7    	  	1536 ms	20.7 MB	C++
7    	  	1688 ms	20.6 MB	C++

でも今運行してタイムアウトを発見して、データを強化しましたね・・・
構想2:二叉探索ツリーの中序的性質を利用して,左右のサブツリーに再帰して平衡二叉探索ツリーを作成する.これはこの問題の正解です.
コード:

class Solution {
public: 
    void InOrderCreateTree(TreeNode*& root, vector<int>& nums, int lo, int hi) {
        if (lo > hi) return ;
        int mid = (lo + hi + 1) / 2;
        root = new TreeNode(nums[mid]);
        InOrderCreateTree(root->left, nums, lo, mid - 1);
        InOrderCreateTree(root->right, nums, mid + 1, hi);
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode *root = NULL;
        InOrderCreateTree(root, nums, 0, nums.size() - 1);
        return root;
    }
};

効率:

    ：24 ms,     C++       90.29%    
    ：21.5 MB,     C++       100.00%