Day15 2022.11.21 搜索与回溯算法（中等）
34.二叉树中和为某一值的路径
自己实现
用递归。递归函数的思路：
- 首先是递归出口
root==NULL时返回-1，告诉上层节点这个地方是NULL，以便于确认上层节点是否为叶子节点。 - 然后将该点放进路径vector中
- 然后向左向右调用
recur，得到相应的返回结果（即判断左右儿子是否为NULL）。 - 如果该节点为叶子节点（左右儿子都是NULL），则判断这条路径的总和是否与
target相符，如果相符就将路径vector放进总的vectorres中
代码如下：
class Solution {
vector<vector<int>> res;
public:
vector<vector<int>> pathSum(TreeNode* root, int target) {
if (root == NULL)return res;
vector<int> vec;
recur(vec, root, target, 0);
return res;
}
int recur(vector<int> vec, TreeNode* root, int target, int before)
{
if (root == NULL)return 1;
vec.push_back(root->val);
int left=recur(vec, root->left, target, before + root->val);
int right=recur(vec, root->right, target, before + root->val);
if (left&&right)
{
if (before + root->val == target)
{
res.push_back(vec);
return 0;
}
}
/*else
{
recur(vec,root->left,target,before+root->val);
recur(vec,root->right,target,before+root->val);
}*/
return 0;
}
};
代码表现
题解
与自己实现的思路大致一样，有细微的改变在于将路径vector作为全局变量而非局部变量，同时减少了向recur()的参数传递，可能vector容器参数的传递会让时间大幅度增长
class Solution {
vector<vector<int>> res;
vector<int> path;
public:
vector<vector<int>> pathSum(TreeNode* root, int target) {
recur(root, target);
return res;
}
void recur(TreeNode *root, int tar) {
if(root == NULL) return;
path.push_back(root->val);
tar -= root->val;
if(tar == 0 && root->left == NULL && root->right == NULL)
res.push_back(path);
recur(root->left, tar);
recur(root->right, tar);
path.pop_back();
}
};
代码表现
hint：
- 注意把一些函数或者赋值写在if判断里面，特别是有
&&的时候，可能会因为判断短路导致后面的判断中的语句没有被运行
36.二叉搜索树与双向链表
自己实现
因为不知道二叉搜索树的这个性质（二叉搜索树按中序遍历是递增的），导致没有思路，直接看题解了
题解
因为二叉搜索树的中序遍历是递增的，所以这个地方可以利用这个性质来构建序列。
具体实现没有很懂，可以看看这个链接来结合理解
代码如下：
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if(root == nullptr) return nullptr;
dfs(root);
head->left = pre;
pre->right = head;
return head;
}
private:
Node *pre, *head;
void dfs(Node* cur) {
if(cur == nullptr) return;
dfs(cur->left);
if(pre != nullptr) pre->right = cur;
else head = cur;
cur->left = pre;
pre = cur;
dfs(cur->right);
}
};
代码表现
hint
- 二叉搜索树的中序遍历序列是所有节点值的递增序列
- 学习中序遍历的递归函数写法
54.二叉搜索树的第k大节点
自己实现
就是上一个题的迷你版，主要是考察二叉搜索树的中序遍历性质，然后考察中序遍历的编写方法
代码如下：
class Solution {
vector<int> vec;
public:
int kthLargest(TreeNode* root, int k) {
dfs(root);
return vec[vec.size()-k];
}
void dfs(TreeNode* root)
{
if(root==NULL)return;
dfs(root->left);
if(root!=NULL)vec.push_back(root->val);
dfs(root->right);
return;
}
};
代码表现
