1.1、题目1
剑指 Offer 54. 二叉搜索树的第k大节点
1.2、解法
res和k设为全局变量，然后开始遍历二叉搜索树，
因为是二叉搜索树，所以从右结点开始遍历，
每次遍历就判断是否到达结点。
每个结点就-k，知道到达结点。
1.3、代码
class Solution {
int res,k;
public int kthLargest(TreeNode root, int k) {
this.k=k;
dfs(root);
return res;
}
public void dfs(TreeNode root){
if(root==null) return ;
dfs(root.right);
if(k==0) return;
if(--k==0) res=root.val;
dfs(root.left);
}
}
2.1、题目2
剑指 Offer 36. 二叉搜索树与双向链表
2.2、解法
深度优先搜索，，通过前后结点开始赋值，
搜索时，中序遍历，如果该结点不为空，
则pre结点的right为当前结点，该节点的left为pre
然后pre结点变为当前节点，到下一个结点继续遍历
2.3、代码
class Solution {
Node pre, head;
public Node treeToDoublyList(Node root) {
if(root == null) return null;
dfs(root);
head.left = pre;
pre.right = head;
return head;
}
void dfs(Node cur) {
if(cur == null) return;
dfs(cur.left);
if(pre != null) pre.right = cur;
else head = cur;
cur.left = pre;
pre = cur;
dfs(cur.right);
}
}
3.1、题目3
剑指 Offer 34. 二叉树中和为某一值的路径
3.2、解法
这里有点像回溯加减枝的感觉
如果到达叶子结点，并且路线结点值加起来是target值就添加入List中
这里结束要将添加的值删除掉，从而进入下个阶段。
3.3、代码
class Solution {
LinkedList<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
recur(root, sum);
return res;
}
void recur(TreeNode root, int tar) {
if(root == null) return;
path.add(root.val);
tar -= root.val;
if(tar == 0 && root.left == null && root.right == null)
res.add(new LinkedList(path));
recur(root.left, tar);
recur(root.right, tar);
path.removeLast();
}
}
原文创作：程序员khaos
原文链接：https://www.cnblogs.com/urmkhaos/p/15272335.html
