地址
- https://www.acwing.com/problem/content/66/
- https://www.acwing.com/problem/content/67/
三道题都是二叉树相关 使用递归遍历即可解决
70. 二叉搜索树的第 k 个结点
给定一棵二叉搜索树, 请找出其中的第 k 小的结点.
你可以假设树和 k 都存在, 并且 1≤k≤树的总结点数.
输入
输入: root = [2, 1, 3, null, null, null, null] ,k = 3
- 2
- / 1 3
输出: 3
中序遍历 额外添加了计数 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 ==0) ans = root;
- travel(root->right,k);
- return NULL;
- }
- TreeNode* kthNode(TreeNode* root, int k) {
- travel(root,k);
- return ans;
- }
- };
- View Code
71. 二叉树的深度
输入一棵二叉树的根结点, 求该树的深度.
从根结点到叶结点依次经过的结点 (含根, 叶结点) 形成树的一条路径, 最长路径的长度为树的深度.
输入
输入: 二叉树 [8, 12, 2, null, null, 6, 4, null, null, null, null] 如下图所示:
- 8
- / 12 2
- / 6 4
输出: 3
递归遍历 添加层数遍历
- /**
- * 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 =0;
- void travel(TreeNode* root,int k){
- if(root == NULL){
- if(k> ans)
- ans =k;
- return;
- }
- travel(root->right,k+1);
- travel(root->left,k+1);
- }
- int treeDepth(TreeNode* root) {
- if(root == NULL) return 0;
- travel(root,0);
- return ans;
- }
- };
- View Code
72. 平衡二叉树
输入一棵二叉树的根结点, 判断该树是不是平衡二叉树.
如果某二叉树中任意结点的左右子树的深度相差不超过 1, 那么它就是一棵平衡二叉树.
注意:
规定空树也是一棵平衡二叉树.
输入
输入: 二叉树 [5,7,11,null,null,12,9,null,null,null,null] 如下所示,
- 5
- / 7 11
- / 12 9
输出: 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+1);
- int r = isBalancedInner(root->right,k+1);
- if(abs(l-r)> 1) ans =false;
- return max(l,r);
- }
- bool isBalanced(TreeNode* root) {
- isBalancedInner(root,0);
- return ans;
- }
- };
- View Code
来源: http://www.bubuko.com/infodetail-3199752.html