代码随想录算法训练营
Day15 代码随想录算法训练营第 15 天 |LeetCode110平衡二叉树 LeetCode257二叉树的所有路径 LeetCode404左叶子之和 LeetCode222完全二叉树节点之和
目录
- 代码随想录算法训练营
- 前言
- 一、基础
- 二、LeetCode110平衡二叉树
- 三、LeetCode257二叉树的所有路径
- 四、LeetCode404左叶子之和
- 五、LeetCode222完全二叉树节点之和
- 总结
前言
LeetCode110平衡二叉树
LeetCode257二叉树的所有路径
LeetCode404左叶子之和
LeetCode222完全二叉树节点之和
一、基础
对于深度和高度的补充：
深度从上向下求，用前序遍历
高度从下向上求，用后序遍历
昨天的最大深度用后序是因为最大深度实际上是根节点的高度
二、LeetCode110平衡二叉树
1.题目链接
2.思路
（1）平衡二叉树的判定：任何一个节点的左右子节点的高度差的绝对值不超过1
（2）求高度：后序
（3）递归
1）参数和返回值
以Node为根节点的子树是平衡二叉树，返回节点高度
以node为根节点的子树不是平衡二叉树，返回-1
2）边界条件
空节点的高度为0
3）单层递归
求左右子节点高度l和r
如果l为-1或者r为-1，则返回-1
如果l与r的差的绝对值大于1，返回-1
返回 l和r的最大值+1
3.题解
class Solution {
public:
int get_height(TreeNode* node) {
if (node == NULL)
return 0;
int l = get_height(node->left);
int r = get_height(node->right);
if (l == -1 || r == -1)
return -1;
if (abs(l - r) > 1)
return -1;
return 1 + max(l, r);
}
bool isBalanced(TreeNode* root) {
int res = get_height(root);
if (res == -1)
return 0;
return 1;
}
};
三、LeetCode257二叉树的所有路径
1.题目链接
2.思路
（1）路径是从根节点开始的，从上到下，所以用前序
（2）递归
1）返回值和参数
参数包括节点指针，答案的引用，路径数组的引用
路径用数组存放便于回溯
2）边界条件
叶节点为边界
将路径数组转换为字符串，放入答案数组
3）单层递归
中：将node的值放入路径数组，这个语句放在最前面，因为叶节点也要存放
左：如果node左节点非空则进行递归调用和回溯
右：如果node右节点非空则进行递归调用和回溯
3.题解
class Solution {
public:
void get_path(TreeNode* node, vector<string>& ans, vector<int>& path) {
path.push_back(node->val);
if (node->left == NULL && node->right == NULL) {
string s;
for (int i = 0; i < path.size() - 1; i++) {
s += to_string(path[i]);
s += "->";
}
s += to_string(path[path.size() - 1]);
ans.push_back(s);
return;
}
if (node->left) {
get_path(node->left, ans, path);
path.pop_back();
}
if (node->right) {
get_path(node->right, ans, path);
path.pop_back();
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> ans;
vector<int> p;
if (root == NULL)
return ans;
get_path(root, ans, p);
return ans;
}
};
四、LeetCode404左叶子之和
1.题目链接
2.思路
（1）左叶子：作为父节点的左子结点的叶节点
用父节点判断左叶子：
(node->left != NULL && node->left->left == NULL &&
node->left->right == NULL
则node->left 为左叶子
（2）递归
1）参数和返回值
参数是节点指针，和指针
2）终止条件：遇到左叶子终止，求和
3）单层递归：判空，递归调用
3.题解
class Solution {
public:
void left_leaves(int* sum, TreeNode* node) {
if (node->left != NULL && node->left->left == NULL &&
node->left->right == NULL) {
*sum += node->left->val;
}
if (node->left)
left_leaves(sum, node->left);
if (node->right)
left_leaves(sum, node->right);
}
int sumOfLeftLeaves(TreeNode* root) {
int sum = 0;
left_leaves(&sum, root);
return sum;
}
};
五、LeetCode222完全二叉树节点之和
1.题目链接
2.普通二叉树做法
遍历+计数
class Solution {
public:
void count(TreeNode * node,int *sum)
{
if(node==NULL)return;
*sum+=1;
count(node->left,sum);
count(node->right,sum);
}
int countNodes(TreeNode* root) {
int ans=0;
count(root,&ans);
return ans;
}
};
3.完全二叉树性质
（1）完全二叉树的定义：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
若r根节点为第一层，最底层为第 h 层，则该层包含 1~ 2 ^（h-1）个节点
（2）递归
1）参数：和的指针，节点指针
2）终止条件：节点为空则深度为0，返回
3）递归
分别求左右子树深度，
如果左右子树深度相同，则以节点为根的子树为满二叉树，用性质求
如果左右子树深度不相同，则以节点为根的子树不为满二叉树，递归调用左右子节点，求左右子树结点数并求和，再+1
class Solution {
public:
void count(TreeNode* node, int* sum) {
if (node == NULL)
return;
TreeNode* l = node->left;
TreeNode* r = node->right;
int l_depth = 0;
int r_depth = 0;
while (l) {
l_depth++;
l = l->left;
}
while (r) {
r_depth++;
r = r->right;
}
if (l_depth == r_depth) {
*sum += (2 << l_depth) - 1;
return;
}
count(node->left, sum);
count(node->right, sum);
*sum += 1;
}
int countNodes(TreeNode* root) {
int sum = 0;
count(root, &sum);
return sum;
}
};
总结
从上向下求，例如求深度和路径，用前序遍历
从下向上求，例如求高度，用后序遍历