Leetcode初级算法

二叉树的层次遍历

对于stack和queue来说是push()，对于vector来说是push_back();

这题最脑坏的部分是，这题是个交错数组，所以要将队列一层出来的值放入vector<int>后再放入vector<vector<int>>

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> Q;
        Q.push(root);
        vector<vector<int>> ans;
        while(!Q.empty()) {
            int len = Q.size();
            vector<int> level;
            while(len--) {
                TreeNode* node = Q.front(); 
                Q.pop();
                if(node == nullptr) 
                    continue;
                level.push_back(node -> val);
                
                if(node -> left != NULL) Q.push(node -> left);
                if(node -> right != NULL) Q.push(node -> right);  
            }
            if(level.size() != 0)
                ans.push_back(level);
        }
        return ans;
    }
};

将有序数组转换为二叉搜索树

首先明确一点，升序数组得到的平衡二叉搜索树是不唯一的，所以会有多种情况。那如何保证得到的二叉搜索树是平衡的呢？可以利用数组下标，对于一个已经升序的数组来说，其数据按下标来都是升序的，那我们就可以用二分的方法，取中间结点为根节点，然后接着二分然后插入，当left 大于 right时，就将结点设为空。

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int len = nums.size();
        return Binaryarray(nums, 0, len - 1);
    }
    TreeNode* Binaryarray(vector<int>& nums, int left, int right) {
        if(left > right) return NULL;
        int mid = (left + right) / 2; //防止溢出
        TreeNode* ans = new TreeNode(nums[mid]);
        ans -> left = Binaryarray(nums, left, mid - 1);
        ans -> right = Binaryarray(nums, mid + 1, right);
        return ans;
    }
};