目录
题目：剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣（Leetcode）
题目：剑指 Offer 55 - I. 二叉树的深度 - 力扣（Leetcode）
题目：剑指 Offer 55 - II. 平衡二叉树 - 力扣（Leetcode）
题目：剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣（Leetcode）
题目的接口：
/**
* 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 kthLargest(TreeNode* root, int k) {
}
};解题思路：
因为平衡二叉树的特点是，走中序遍历是一个升序数组，
题目要求找出第k大的值，
那不难想到，我们只需要倒着中序遍历平衡二叉树就行，
每次让k--，只要k==0就表明找到了：
代码：
/**
* 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 kthLargest(TreeNode* root, int k) {
//走中序遍历
dfs(root, k);
return ans;
}
private:
//记录k节点的值
int ans = 0;
//走一个倒序的中序遍历，让k值每走一个节点就--
void dfs(TreeNode* root, int& k) {
if(root == nullptr) return;
dfs(root->right, k);
//找到题目要求节点，记录ans值
if(--k == 0) {
ans = root->val;
return;
}
dfs(root->left, k);
}
};过啦！！！
题目：剑指 Offer 55 - I. 二叉树的深度 - 力扣（Leetcode）
题目的接口：
/**
* 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 maxDepth(TreeNode* root) {
}
};解题思路：
我的思路是，计算每一个子树的左右子树的深度，
然后比较每一个左右子树的深度，保存最大值，
具体解析如图所示：
通过不断计算每个子树的最大深度，
最后得出整棵树的最大深度
下面是代码：
代码：
/**
* 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 maxDepth(TreeNode* root) {
if(root == nullptr) return 0;
int left = maxDepth(root->left); //求出左边高度
int right = maxDepth(root->right); //求出右边高度
return max(left, right) + 1; //每层 + 1
}
};过啦！！！
题目：剑指 Offer 55 - II. 平衡二叉树 - 力扣（Leetcode）
题目的接口：
/**
* 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 isBalanced(TreeNode* root) {
}
};解题思路：
具体思路是，
我们通过计算左右子树的最大深度差，
如果左右子树的最大深度差 >= 2 证明不是平衡二叉树，
如果 < 2 就证明这个子树本身是平衡二叉树，那就正常计算自身的最大深度，
一直到根节点的左右子树依然没有返回 -1 深度符合要求，证明是平衡二叉树，
如果返回了 -1 就证明不是平衡二叉树，
这里计算最大深度的思想也沿用了上一题的思路，
下面是代码：
代码：
/**
* 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 isBalanced(TreeNode* root) {
//判断如果返回-1就证明不是平衡二叉树
return recur(root) != -1;
}
private:
int recur(TreeNode* root) {
if(root == nullptr) return 0;
//计算左右子树最大深度，如果出现-1证明不是平衡二叉树，返回-1就行
int left = recur(root->left);
if(left == -1) return -1;
int right = recur(root->right);
if(right == -1) return -1;
//核心代码：如果左右子树最大深度正常，就正常计算左右深度的最大值
//如果左右子树的最大深度差大于2，就证明这不是一个平衡二叉，返回-1
return abs(left - right) < 2 ? max(left, right) + 1 : -1;
}
};过啦！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看