1. 平衡二叉树
代码随想录: 原文
力扣题目: 110.平衡二叉树
1.1 思路
代码的逻辑其实是求的根节点的高度,而根节点的高度就是这棵树的最大深度,使用后序遍历。
1.1.1 递归
1. 明确递归函数的参数和返回值
- 参数:当前传入节点
- 返回值:以当前传入节点为根节点的树的高度
- 当前传入节点为根节点的二叉树已经不是二叉平衡树,可以返回-1 来标记已经不符合平衡树的规则了
// -1 表示已经不是平衡二叉树了,否则返回值是以该节点为根节点树的高度
int getHeight(TreeNode* node)
2. 明确终止条件
递归的过程中依然是遇到空节点了为终止,返回0
if (node == NULL) {
return 0;
}
3. 明确单层递归的逻辑
分别求出其左右子树的高度,然后如果差值小于等于1,则返回当前二叉树的高度,否则返回-1
int leftHeight = getHeight(node->left); // 左
if (leftHeight == -1) return -1;
int rightHeight = getHeight(node->right); // 右
if (rightHeight == -1) return -1;
int result;
if (abs(leftHeight - rightHeight) > 1) { // 中
result = -1;
} else {
result = 1 + max(leftHeight, rightHeight); // 以当前节点为根节点的树的最大高度
}
return result;
这个递归的函数传入节点指针,返回以该节点为根节点的二叉树的高度,如果不是二叉平衡树,则返回-1
1.1.2 迭代
- 先定义一个函数,专门用来求高度
- 函数通过栈模拟的后序遍历找每一个节点的高度
- 再用栈来模拟后序遍历,遍历每一个节点的时候,再去判断左右孩子的高度是否符合
1.2 代码实现
class Solution {
public:
// 返回以该节点为根节点的二叉树的高度,如果不是平衡二叉树了则返回-1
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. 二叉树的所有路径
2.1 思路
前序遍历以及回溯的过程如图:
1. 递归函数参数以及返回值
- 要传入根节点
- 记录每一条路径的path
- 存放结果集的result
- 这里递归不需要返回值
void traversal(TreeNode* cur, vector<int>& path, vector<string>& result)
2. 确定递归终止条件
当 cur不为空,其左右孩子都为空的时候,就找到叶子节点
if (cur->left == NULL && cur->right == NULL) {
终止处理逻辑
}
- 使用vector 结构path来记录路径
- 要把vector 结构的path转为string格式
- 再把这个string 放进 result里
- 使用vector结构的path容器来记录路径,那么终止处理逻辑如下:
if (cur->left == NULL && cur->right == NULL) { // 遇到叶子节点
string sPath;
for (int i = 0; i < path.size() - 1; i++) { // 将path里记录的路径转为string格式
sPath += to_string(path[i]);
sPath += "->";
}
sPath += to_string(path[path.size() - 1]); // 记录最后一个节点(叶子节点)
result.push_back(sPath); // 收集一个路径
return;
}
3. 确定单层递归逻辑
- 前序遍历,需要先处理中间节点,中间节点就是我们要记录路径上的节点,先放进path中
- 递归前要加上判断语句,下面要递归的节点是否为空
if (cur->left) {
traversal(cur->left, path, result);
}
if (cur->right) {
traversal(cur->right, path, result);
}
回溯和递归是一一对应的,有一个递归,就要有一个回溯,回溯要和递归永远在一起
if (cur->left) {
traversal(cur->left, path, result);
path.pop_back(); // 回溯
}
if (cur->right) {
traversal(cur->right, path, result);
path.pop_back(); // 回溯
}
2.2 代码实现
class Solution {
private:
void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
path.push_back(cur->val); // 中,中为什么写在这里,因为最后一个节点也要加入到path中
// 这才到了叶子节点
if (cur->left == NULL && cur->right == NULL) {
string sPath;
for (int i = 0; i < path.size() - 1; i++) {
sPath += to_string(path[i]);
sPath += "->";
}
sPath += to_string(path[path.size() - 1]);
result.push_back(sPath);
return;
}
if (cur->left) { // 左
traversal(cur->left, path, result);
path.pop_back(); // 回溯
}
if (cur->right) { // 右
traversal(cur->right, path, result);
path.pop_back(); // 回溯
}
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
vector<int> path;
if (root == NULL) return result;
traversal(root, path, result);
return result;
}
};
补充:
if (cur->left) traversal(cur->left, path + "->", result); // 左 回溯就隐藏在这里
改为
path += "->";
traversal(cur->left, path, result); // 左
把 path + "->"作为函数参数就是可以的,因为并没有改变path的数值,执行完递归函数之后,path依然是之前的数值(相当于回溯了)
3. 左叶子之和
代码随想录: 原文
力扣题目: 404.左叶子之和
3.1 思路
左叶子定义:
- 节点A的左孩子不为空
- 左孩子的左右孩子都为空(说明是叶子节点)
判断当前节点是不是左叶子是无法判断的,必须要通过节点的父节点来判断其左孩子是不是左叶子
1. 确定递归函数的参数和返回值
- 那么一定要传入树的根节点
- 递归函数的返回值为数值之和
2. 确定终止条件
如果遍历到空节点,那么左叶子值一定是0
if (root == NULL) return 0;
只有当前遍历的节点是父节点,才能判断其子节点是不是左叶子。 所以如果当前遍历的节点是叶子节点,那其左叶子也必定是0,那么终止条件为:
if (root == NULL) return 0;
if (root->left == NULL && root->right== NULL) return 0; //其实这个也可以不写,如果不写不影响结果,但就会让递归多进行了一层。
3. 确定单层递归的逻辑
- 左叶子节点的时候,记录数值
- 通过递归求取左子树左叶子之和,和右子树左叶子之和,相加便是整个树的左叶子之和
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;
3.2 代码实现
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. 总结
- 初学者先将算法流程搞清楚再代码精简
- 仍需二刷迭代法
- 回溯要和递归永远在一起
学习时间:120min
评论区