剑指 Offer 34. 二叉树中和为某一值的路径
题目描述
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点是指没有子节点的节点。
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]题目链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
思路
深度优先遍历（DFS），采用前序遍历的方式，从根节点遍历到叶子节点，用集合记录遍历过程中的节点值，并进行累加，遇到叶子节点时就与给定的目标和进行比较，相等就将集合中的元素存入结果集合中，注意在回溯过程中需要移除集合中的当前节点。
实现代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
dfs(root, target, 0, new ArrayList<>());
return res;
}
public void dfs(TreeNode root, int target, int sum, List<Integer> list){
if(root == null){
return;
}
sum += root.val; //累加节点值
list.add(root.val); //加入集合
if(root.left == null && root.right == null){
//到达根节点时就判断从从根节点到叶子节点的节点累加值是否等于目标值
if(sum == target){
res.add(new ArrayList<>(list)); //不能直接返回list，需将其中的元素赋给一个新集合
list.remove(list.size() - 1);
return;
}
}
dfs(root.left, target, sum, list);
dfs(root.right, target, sum, list);
//在回溯过程中需移除当前节点，即当前集合的最后一个节点（最新加入的）
list.remove(list.size() - 1);
}
}
剑指 Offer 36. 二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
思路
将 二叉搜索树 转换成一个 “排序的循环双向链表” ，其中包含三个要素：
- 排序链表： 使用中序遍历可“从小到大”访问二叉搜索树中的节点。
-
双向链表： 在构建相邻节点的引用关系时，设置前驱节点 pre 和当前节点 cur ，以此构建pre的后继指针指向当前节点，即
，当前节点的前驱指针指向pre，即
。
-
循环链表： 设链表头节点 head 和尾节点 tail （pre遍历到最后会成为尾节点），则应构建
和
。
实现代码
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
Node head, pre;
public Node treeToDoublyList(Node root) {
if(root == null){
return null;
}
dfs(root);
//链表头节点的前驱指针需指向尾节点，尾节点的后继指针指向头节点
head.left = pre;
pre.right = head;
return head;
}
public void dfs(Node cur){ //中序遍历
if(cur == null){
return;
}
dfs(cur.left);
//pre用于记录双向链表中位于cur左侧的节点，即上一次迭代中的cur
if(pre == null){
//当pre==null时，cur左侧没有节点,则此时cur为双向链表中的头节点
head = cur;
}else{ //否则需相互指向
cur.left = pre;
pre.right = cur;
}
pre = cur; //pre指向当前节点
dfs(cur.right);
}
}
剑指 Offer 54. 二叉搜索树的第k大节点
题目描述
给定一棵二叉搜索树，请找出其中第k大的节点。
输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 4题目链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
方法一：中序遍历得到有序序列
二叉搜索树的中序遍历可得到有序序列，通过下标直接返回，这种做法的时间复杂度较大，显然不是最好的方法。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int kthLargest(TreeNode root, int k) {
List<Integer> list = new ArrayList<>();
inOrderTra(root, list);
return list.get(list.size() - k);
}
public void inOrderTra(TreeNode root, List<Integer> list){
if(root == null){
return;
}
inOrderTra(root.left, list);
list.add(root.val);
inOrderTra(root.right, list);
}
}
方法二：中序遍历的倒序
先中序遍历得到有序序列序会耗费较多的时间，能够在中序遍历的过程中就把结果找到显然是最好的，方法如下：
按中序遍历的倒序 “右、根、左” 顺序遍历，可得到二叉搜索树的倒序，即从大到小的顺序，则第K大即为第K个元素，因此只需返回遍历到的第K个元素即可。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int count, res;
public int kthLargest(TreeNode root, int k) {
this.count = k;
inOrderTra(root);
return res;
}
//按中序遍历的倒序 “右、根、左” 顺序遍历，可得到二叉搜索树的倒序，则第K大即为第K个元素
public void inOrderTra(TreeNode root){
if(root == null || count == 0){
return;
}
inOrderTra(root.right);
if(--count == 0){
res = root.val;
return;
}
inOrderTra(root.left);
}
}
京公网安备 11010502036488号