代码随想录算法训练营
Day16 代码随想录算法训练营第 16 天 |LeetCode112路径总和 LeetCode113路径总和ii LeetCode106.从中序与后序遍历序列构造二叉树 LeetCode105.从前序与中序遍历序列构造二叉树
目录
- 代码随想录算法训练营
- 前言
- 一、LeetCode112路径总和
- 二、LeetCode113路径总和ii
- 三、LeetCode106.从中序与后序遍历序列构造二叉树
- 四、LeetCode105从前序与中序遍历序列构造二叉树
- 总结
前言
LeetCode112路径总和,LeetCode113路径总和ii
LeetCode106.从中序与后序遍历序列构造二叉树LeetCode105从前序与中序遍历序列构造二叉树
一、LeetCode112路径总和
1.题目链接
2.思路
（1）和路径问题一样的思路，前序遍历
（2）递归实现
1）参数：节点指针，路径数组引用，targetsum，和指针
2）终止条件：叶节点终止，求和，与targetsum比较，如果相等，则总数+1
3）单层递增：
中：存放路径（第一句进行存放，因为叶节点就要存放）
左：递归调用，回溯
右：递归调用，回溯
为什么在递归调用之前先判断是否为空指针
如果先判断Node非空，不在递归调用之前先判断是否为空指针
p(node->left, path, targetsum, ans);
path.pop_back();
p(node->right, path, targetsum, ans);
path.pop_back();
这样如果node->left是空节点，不会加到路径里面，但是还会进行pop_back
3.题解
class Solution {
public:
void p(TreeNode* node, vector<int>& path, int targetsum, int* ans) {
path.push_back(node->val);
if (node->left == NULL && node->right == NULL) {
int n = path.size();
int s = 0;
for (int i = 0; i < n; i++) {
s += path[i];
}
if (s == targetsum)
(*ans) += 1;
return;
}
if (node->left != NULL) {
p(node->left, path, targetsum, ans);
path.pop_back();
}
if (node->right != NULL) {
p(node->right, path, targetsum, ans);
path.pop_back();
}
}
bool hasPathSum(TreeNode* root, int targetSum) {
int ans = 0;
vector<int> path;
if(root==NULL) return 0;
p(root, path, targetSum, &ans);
if (ans > 0)
return 1;
else
return 0;
}
};
二、LeetCode113路径总和ii
1.题目链接
2.思路
（1）在LeetCode112路径总和的思路上修改
（2）每次到叶子结点时，将路径存放进数组，如果路径之和为targetsum的，则加入二维数组
3.题解
class Solution {
public:
void p(TreeNode* node, vector<int>& path, int targetsum,
vector<vector<int>>& ans) {
path.push_back(node->val);
if (node->left == NULL && node->right == NULL) {
int n = path.size();
int s = 0;
vector<int> res;
for (int i = 0; i < n; i++) {
s += path[i];
res.push_back(path[i]);
}
if (s == targetsum)
ans.push_back(res);
return;
}
if (node->left != NULL) {
p(node->left, path, targetsum, ans);
path.pop_back();
}
if (node->right != NULL) {
p(node->right, path, targetsum, ans);
path.pop_back();
}
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> ans;
vector<int> path;
if (root == NULL)
return ans;
p(root, path, targetSum, ans);
return ans;
}
};
三、LeetCode106.从中序与后序遍历序列构造二叉树
1.题目链接
2.思路
（1）每次后序数组最后一个元素为子树根节点
以后序数组最后一个元素为切割点，先切割中序数组，再用中序数组切割后序数组
（2）步骤
1）边界条件：如果数组大小为0，说明是空节点
2）如果数组不为空，以后续数组最后一个元素为子树根节点，
再判断数组长度是否为1，如果数组长度为1，说明已经是二叉树的根节点，返回
3）求后序数组最后一个元素在中序数组中的位置
4）切割中序数组：得到中序左数组，中序右数组
5）切割后序数组：得到后序左数组，后序右数组，确保中序左数组与后序左数组长度一致
6）递归，求左子结点，右子节点
3.题解
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (postorder.size() == 0 || inorder.size() == 0)
return NULL;
int value = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(value);
if (postorder.size() == 1)
return root;
int index;
for (index = 0; index < inorder.size(); index++) {
if (inorder[index] == value)
break;
}
vector<int> inorder_left(inorder.begin(), inorder.begin() + index);
vector<int> inorder_right(inorder.begin() + index + 1, inorder.end());
postorder.pop_back();
vector<int> postorder_left(postorder.begin(),
postorder.begin() + index);
vector<int> postorder_right(postorder.begin() + index, postorder.end());
root->left = buildTree(inorder_left, postorder_left);
root->right = buildTree(inorder_right, postorder_right);
return root;
}
};
四、LeetCode105从前序与中序遍历序列构造二叉树
1.题目链接
2.思路
1）每次前序数组最后一个元素为子树根节点
以前序数组最后一个元素为切割点，先切割中序数组，再用中序数组切割前序数组
（2）步骤
1）边界条件：如果数组大小为0，说明是空节点
2）如果数组不为空，以后续数组最后一个元素为子树根节点，
再判断数组长度是否为1，如果数组长度为1，说明已经是二叉树的根节点，返回
3）求前序数组最后一个元素在中序数组中的位置
4）切割中序数组：得到中序左数组，中序右数组
5）切割前序数组：得到前序左数组，前序右数组，确保中序左数组与前序左数组长度一致
6）递归，求左子结点，右子节点
注意：切割是与LeetCode106不同的，不制作新的数组，而是移动起点和终点的指针，实际上中序数组和前序数组实际上没改变
为什么：数组不能从前端弹出元素
3.题解
class Solution {
public:
TreeNode* trace(vector<int>& preorder, int preorder_head, int preorder_end,
vector<int>& inorder, int inorder_head, int inorder_end) {
if (preorder_end == preorder_head)
return NULL;
if (inorder_end == inorder_head)
return NULL;
int value = preorder[preorder_head];
TreeNode* root = new TreeNode(value);
if (preorder_end - preorder_head == 1)
return root;
int index;
for (index = inorder_head; index < inorder_end; index++) {
if (inorder[index] == value)
break;
}
int inorder_left_head = inorder_head;
int inorder_left_end = index;
int inorder_right_head = index + 1;
int inorder_right_end = inorder_end;
int preorder_left_head = preorder_head + 1;
int preorder_left_end = preorder_head + index - inorder_head + 1;
int preorder_right_head = preorder_head + index - inorder_head + 1;
int preorder_right_end = preorder_end;
root->left = trace(preorder, preorder_left_head, preorder_left_end,
inorder, inorder_left_head, inorder_left_end);
root->right = trace(preorder, preorder_right_head, preorder_right_end,
inorder, inorder_right_head, inorder_right_end);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.size() == 0 || inorder.size() == 0)
return NULL;
return trace(preorder, 0, preorder.size(), inorder, 0, inorder.size());
}
};
总结
1、路径之和：与昨天的路径问题思路相似，前序递归
每次遇到叶子结点时求路径之和并进行比较
2、数组构造二叉树
（1）前序数组的第一个元素为子树根节点，由于数组不可以从前端弹出元素，分割数组是通过指针移动实现的，不产生新的数组
（2）后续数组最后一个元素为子树根节点,分割数组产生新的数组