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; } };