acwing 70-72 剑指OFFER 二叉树相关
2024-09-06 08:22:29
地址
https://www.acwing.com/problem/content/66/
https://www.acwing.com/problem/content/67/
https://www.acwing.com/problem/content/submission/68/
三道题都是二叉树相关 使用递归遍历即可解决
70. 二叉搜索树的第k个结点
给定一棵二叉搜索树，请找出其中的第k小的结点。
你可以假设树和k都存在，并且1≤k≤树的总结点数。
输入
输入：root = [, , , null, null, null, null] ，k = / \ 输出：
中序遍历 额外添加了计数K
当遍历了K个节点 就找到了目标节点
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* ans;
TreeNode* travel(TreeNode* root, int& k)
{
if(root == NULL) return NULL; travel(root->left,k);
k--;
if(k ==) ans = root; travel(root->right,k); return NULL;
} TreeNode* kthNode(TreeNode* root, int k) {
travel(root,k); return ans;
}
};
71. 二叉树的深度
输入一棵二叉树的根结点，求该树的深度。
从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
输入
输入：二叉树[, , , null, null, , , null, null, null, null]如下图所示：
/ \
/ \
输出：
递归遍历 添加层数遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int ans =; void travel(TreeNode* root,int k){
if(root == NULL){
if(k > ans)
ans =k;
return;
}
travel(root->right,k+);
travel(root->left,k+); } int treeDepth(TreeNode* root) {
if(root == NULL) return ;
travel(root,); return ans;
}
};
72. 平衡二叉树
输入一棵二叉树的根结点，判断该树是不是平衡二叉树。
如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
注意：
- 规定空树也是一棵平衡二叉树。
输入
输入：二叉树[,,,null,null,,,null,null,null,null]如下所示，
/ \
/ \
输出：true
递归遍历 记录每个节点作为子树的深度 向上返回左右子树大的那个深度
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool ans =true;
int isBalancedInner(TreeNode* root,int k)
{
if(root == NULL) return k; int l = isBalancedInner(root->left,k+);
int r = isBalancedInner(root->right,k+); if(abs(l-r) > ) ans =false; return max(l,r);
} bool isBalanced(TreeNode* root) {
isBalancedInner(root,); return ans;
}
};
最新文章
- goim socket丢包粘包问题解决。
- flask-admin章节一：使用chartkick画报表
- jq 修改input 标签的值
- JavaWeb学习笔记——第一个JSP文件
- Magicodes.WeiChat——使用AntiXssAttribute阻止XSS（跨站脚本攻击）攻击
- DataFrame使用mysql数据
- scala vs java 相同点和差异
- bzoj 2843 极地旅行社（LCT）
- IE JavaScript字符串转换成Date后出现NaN错误
- C库专题(Day1)
- ASPNET程序中常用的三十三种代码
- Git merge local repository
- Windows Phone – 裁剪图片 (Crop Image)
- USACO 2017 February Gold
- Op-level的快速算法
- Tomcat架构解析(五)-----Tomcat的类加载机制
- 【JMeter】基础元件
- webpack 多页面|入口支持和公共组件单独打包--转载
- bzoj 3676 后缀自动机+马拉车+树上倍增
- 通过HttpWebRequest实现模拟登陆