剑指offer day15 搜索与回溯算法（中等）
day15题目：剑指 Offer 34. 二叉树中和为某一值的路径、剑指 Offer 36. 二叉搜索树与双向链表、剑指 Offer 54. 二叉搜索树的第k大节点
知识点：树、深搜、栈，难度为中等、中等、简单
学习计划链接：「剑指 Offer」 - 学习计划
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
示例 2：
示例 3：
提示：
树中节点总数在范围
[0, 5000]内-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/
思路
d！都可以d！
通过dfs，每次传递当前结点和路径和
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
注意： 本题与主站 426 题相同：https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
注意： 此题对比原题有改动。
思路
题目要求节点应从小到大排序，而二叉搜索树的中序遍历是递增的，故中序遍历的同时构建相邻节点的引用关系，注意的是prev和head一开始都为null，直到找到第一个节点时head才被置为第一个结点，然后将prev置为当前节点。所以dfs完后还需进行尾部与头节点的一个连接
给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
示例 1:
示例 2:
限制：
1 ≤ k ≤ 二叉搜索树元素个数
思路
上题也说了，二叉搜索树中序遍历是递增的，而先访问右侧结点的话，右中左则是递减的，因此取k个就好了。
最后更新于
这有帮助吗？