算法刷题：LC初级算法（五）
文章目录
二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7返回它的最大深度 3 。
作者：力扣 (LeetCode) 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnd69e/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
思路：很直接，递归那一套。
int maxDepth(TreeNode* root) {
if(root == NULL)
return 0;
return 1+max(maxDepth(root->left),maxDepth(root->right));
}验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。示例 1:
输入:
2
/ \
1 3
输出: true示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。
作者：力扣 (LeetCode) 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn08xg/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
思路： 对于这种二叉树，前序遍历取出来就是一个升序数列。
void mrun(vector<int>& temp,TreeNode* root){
if(root == NULL)
return;
mrun(temp,root->left);
temp.push_back(root->val);
mrun(temp,root->right);
}
bool isValidBST(TreeNode* root) {
vector<int> temp;
mrun(temp,root);
for(int x = 0;x<temp.size()-1;x++){
if(temp[x]>=temp[x+1])
return false;
}
return true;
}对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
作者：力扣 (LeetCode) 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn7ihv/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
我用的是迭代的方式，将根的左右子树分别前序遍历和反前序遍历之后进行比对，但是这样会耗费一部分的存储空间。
void frrun(vector<int>& temp,TreeNode* root){
if(root == NULL){
temp.push_back(INT_MIN);
return;
}
temp.push_back(root->val);
frrun(temp,root->right);
frrun(temp,root->left);
}
void flrun(vector<int>& temp,TreeNode* root){
if(root == NULL)if(root == NULL){
temp.push_back(INT_MIN);
return;
}
temp.push_back(root->val);
flrun(temp,root->left);
flrun(temp,root->right);
}
bool isSymmetric(TreeNode* root) {
vector<int> temp1;
vector<int> temp2;
frrun(temp1,root->right);
flrun(temp2,root->left);
if(temp1.size() != temp2.size())
return false;
for(int x = 0;x<temp1.size();x++)
if(temp1[x] != temp2[x])
return false;
return true;
}二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例： 二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]作者：力扣 (LeetCode) 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnldjj/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> target;
if(!root)
return target;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
// 当前队列中的元素都是同一层的，n为该层元素数目
int n = que.size();
// 定义一个容器存储该层的节点的val值
vector<int> tv;
while(n--){
TreeNode* tn = que.front(); que.pop();
tv.push_back(tn->val);
if(tn->left)
que.push(tn->left);
if(tn->right)
que.push(tn->right);
}
target.push_back(tv);
}
return target;
}将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
这不就是我的面试题里面的一部分嘛、
TreeNode* check(vector<int>& nums, int Left, int Right) {
if(Left > Right) {
return nullptr;
}
int Mid = (Right + Left)/2;
TreeNode * ret = new TreeNode(nums[Mid]);
ret->left = check(nums, Left, Mid-1);
ret->right = check(nums, Mid+1, Right);
return ret;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return check(nums, 0, nums.size()-1);
}腾讯云开发者
