题目：剑指 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; } };
过啦！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看
