DFS + iteration


  • 0
    N

    1 DFS

    class Solution {
    public:
        TreeNode* sortedArrayToBST(vector<int>& nums) {
            //insert from middle
            return recursion(nums, 0, nums.size() - 1);
        }
        
        TreeNode* recursion(vector<int>& nums, int i, int j) {
            if (i > j)
                return NULL;
            int mid = i + (j - i) / 2;
            TreeNode* root = new TreeNode(nums[mid]);
            root->left = recursion(nums, i, mid - 1);
            root->right = recursion(nums, mid + 1, j);
            
            return root;
        }
    };
    

    2 iteration

     struct Tree {
       int low;
       int high;
       TreeNode * node;
       Tree(int _low, int _high, TreeNode* _node) : low(_low), high(_high), node(_node) {}
     };
    class Solution {
    public:
        TreeNode* sortedArrayToBST(vector<int>& nums) {
            if (nums.size() == 0)
                return NULL;
            int mid;
            stack<Tree*> s;
            TreeNode* root = new TreeNode(nums[(nums.size() - 1)/2]);
            Tree* tree = new Tree(0, nums.size() - 1, root), *tmp = NULL;
            s.push(tree);
            while (!s.empty()) {
                tmp = s.top();
                s.pop();
                mid = tmp->low + (tmp->high - tmp->low) / 2;
                if (tmp->low < mid) {
                    TreeNode* node = new TreeNode(nums[tmp->low + (mid - 1 - tmp->low) / 2]);
                    tmp->node->left = node;
                    tree = new Tree(tmp->low, mid - 1, node);
                    s.push(tree);
                }
                
                if (mid < tmp->high) {
                    TreeNode* node = new TreeNode(nums[mid + 1 + (tmp->high - mid - 1)/2]);
                    tmp->node->right = node;
                    tree = new Tree(mid + 1, tmp->high, node);
                    s.push(tree);
                }            
            }
            
            return root;   
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.