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;
    }
};

代码表现

原文地址：http://www.cnblogs.com/cspzyy/p/16928493.html