算法刷题：LC初级算法（五）
二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3 / \
9 20 / \ 15 7
- 1
- 2
- 3
- 4
- 5
返回它的最大深度 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
- 3
- 4
- 5
验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
- 1
- 2
- 3
示例 1:
输入:
2 / \
1 3
输出: true
- 1
- 2
- 3
- 4
示例 2:
输入:
5 / \
1 4 / \ 3 6
输出: false
- 1
- 2
- 3
- 4
- 5
- 6
解释: 输入为: [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
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1 / \
2 2
/ \ / \
3 4 4 3
- 1
- 2
- 3
- 4
- 5
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1 / \
2 2 \ \ 3 3
- 1
- 2
- 3
- 4
- 5
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
作者：力扣 (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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3 / \
9 20 / \ 15 7
- 1
- 2
- 3
- 4
- 5
返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]
- 1
- 2
- 3
- 4
- 5
作者：力扣 (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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
将有序数组转换为二叉搜索树
给你一个整数数组 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);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。
原文链接：lion-wu.blog.csdn.net/article/details/116504225
- 点赞
- 收藏
- 关注作者
评论（0）