acwing 70-72 剑指OFFER 二叉树相关
2021-02-03 00:13
标签：地址 平衡 二叉树 abs oid init 假设 bin col 地址 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≤树的总结点数。 输入 中序遍历 额外添加了计数K 当遍历了K个节点 就找到了目标节点 71. 二叉树的深度 输入一棵二叉树的根结点，求该树的深度。 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 输入 递归遍历 添加层数遍历 72. 平衡二叉树 输入一棵二叉树的根结点，判断该树是不是平衡二叉树。 如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。 注意： 输入 递归遍历 记录每个节点作为子树的深度 向上返回左右子树大的那个深度 acwing 70-72 剑指OFFER 二叉树相关 标签：地址 平衡 二叉树 abs oid init 假设 bin col 原文地址：https://www.cnblogs.com/itdef/p/11525063.html输入：root = [2, 1, 3, null, null, null, null] ，k = 3
2
/ 1 3
输出：3
1 /**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 TreeNode* ans;
13 TreeNode* travel(TreeNode* root, int& k)
14 {
15 if(root == NULL) return NULL;
16
17 travel(root->left,k);
18 k--;
19 if(k ==0) ans = root;
20
21 travel(root->right,k);
22
23
24 return NULL;
25 }
26
27 TreeNode* kthNode(TreeNode* root, int k) {
28 travel(root,k);
29
30 return ans;
31 }
32 };
输入：二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示：
8
/ 12 2
/ 6 4
输出：3
1 /**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 int ans =0;
13
14 void travel(TreeNode* root,int k){
15 if(root == NULL){
16 if(k > ans)
17 ans =k;
18 return;
19 }
20 travel(root->right,k+1);
21 travel(root->left,k+1);
22
23 }
24
25 int treeDepth(TreeNode* root) {
26 if(root == NULL) return 0;
27 travel(root,0);
28
29
30 return ans;
31 }
32 };
输入：二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示，
5
/ 7 11
/ 12 9
输出：true
1 /**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 bool ans =true;
13 int isBalancedInner(TreeNode* root,int k)
14 {
15 if(root == NULL) return k;
16
17 int l = isBalancedInner(root->left,k+1);
18 int r = isBalancedInner(root->right,k+1);
19
20 if(abs(l-r) > 1) ans =false;
21
22 return max(l,r);
23 }
24
25 bool isBalanced(TreeNode* root) {
26 isBalancedInner(root,0);
27
28 return ans;
29 }
30 };
下一篇：C# 保存文件
文章标题：acwing 70-72 剑指OFFER 二叉树相关
文章链接：http://soscw.com/index.php/essay/50165.html