1、110平衡二叉树
给定一个二叉树，判断它是否是平衡二叉树。
平衡二叉树：指该树所有节点的左右子树的高度相差不超过1。
我的思路：这道题和最大深度不同，最大深度只需要递归返回最大深度，但是这里有两个信息需要返回，一个是返回节点高度来供父节点处理，二是当前节点不满足平衡就返回false。我把高度作为参数，返回值为是否平衡。
代码随想录：看了代码随想录，由于高度始终为正，所以可以把-1作为否平衡，>0作为平衡。这样就只需要一个返回值，也就是当前节点的高度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
class Solution {
public:
bool traverse(TreeNode* root,int &hig){
if(root == nullptr){
hig = 0;
return true;
}
int higl = 0,higr = 0;
if(traverse(root->left,higl) == false ||
traverse(root->right,higr) == false){
return false;
}
if(std::abs(higl-higr)>1)return false;
hig = 1+std::max(higl,higr);
return true;
}
bool isBalanced(TreeNode* root) {
int hig = 0;
return traverse(root,hig);
}
};
class Solution {
public:
int getHeight(TreeNode* node) {
if (node == NULL) {
return 0;
}
int leftHeight = getHeight(node->left);
if (leftHeight == -1) return -1;
int rightHeight = getHeight(node->right);
if (rightHeight == -1) return -1;
return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
}
bool isBalanced(TreeNode* root) {
return getHeight(root) == -1 ? false : true;
}
};
|
2、257二叉树的所有路径
给你一个二叉树的根节点 root ，按任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点是指没有子节点的节点。
我的思路： 我觉得这题的关键在于路径是从root指向叶子节点，也就是从上到下，所以可以使用前序遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
void traverse(TreeNode* root, vector<int> &path, vector<string>& res){
if(root == nullptr) return;
path.emplace_back(root->val);
if(root->left == nullptr && root->right == nullptr){
string temp;
for(int i = 0;i<path.size()-1;i++){
temp+=std::to_string(path[i])+"->";
}
temp+=std::to_string(root->val);
path.pop_back();
res.emplace_back(temp);
return;
}
traverse(root->left,path,res);
traverse(root->right,path,res);
path.pop_back();
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<int> path;
vector<string> res;
traverse(root,path,res);
return res;
}
};
|
3、404左叶子之和
给定二叉树的根节点 root ，返回所有左叶子之和。
我的思路： 递归的第一要素就是找到截止条件，一般遍历判断当前节点是否为空指针即可，但是对于一些特殊情况，比如要求左叶子节点就必须找到父节点。
代码随想录递归三部曲：
- 确定递归函数的参数和返回值
- 确定终止条件
- 确定单层递归的逻辑
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
class Solution {
public:
int traverse(TreeNode* root){
int le = 0,ri = 0;
if(root->left != nullptr){
if(root->left->left == nullptr && root->left->right == nullptr){
le = root->left->val;
}else{
le = traverse(root->left);
}
}
if(root->right != nullptr){
ri = traverse(root->right);
}
return le+ri;
}
int sumOfLeftLeaves(TreeNode* root) {
if(root == nullptr)return 0;
return traverse(root);
}
};
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right== NULL) return 0;
int leftValue = sumOfLeftLeaves(root->left);
if (root->left && !root->left->left && !root->left->right) {
leftValue = root->left->val;
}
int rightValue = sumOfLeftLeaves(root->right);
int sum = leftValue + rightValue;
return sum;
}
};
|
4、222完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树定义：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。
我的思路： 这道题第一眼看起来和求普通二叉树节点个数一样。选定返回值为当前节点以下的个数，则确定使用后序遍历。
代码随想录： 完全二叉树中大部分子树为满二叉树，对于满二叉树我们通过它的深度即可计算出节点个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
class Solution {
public:
int countNodes(TreeNode* root) {
if(root == nullptr)return 0;
int le = countNodes(root->left);
int ri = countNodes(root->right);
return 1+le+ri;
}
};
class Solution {
public:
int countNodes(TreeNode* root) {
if(root == nullptr)return 0;
TreeNode* left = root->left;
int leftdep = 0;
while(left!=nullptr){
left = left->left;
leftdep++;
}
TreeNode* right = root->right;
int rightdep = 0;
while(right!=nullptr){
right = right->right;
rightdep++;
}
if(leftdep == rightdep){
return (2 << leftdep) - 1;
}
return 1 + countNodes(root->left)+countNodes(root->right);
}
};
|
代码随想录算法训练第十五天|110平衡二叉树|257二叉树的所有路径|404左叶子之和|222完全二叉树的节点个数
