【LeetCode】剑指 Offer（28）
目录
题目：剑指 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，就证明这不是一个平衡二叉，返回-1return abs(left - right) < 2 ? max(left, right) + 1 : -1; }
};过啦！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看
