目录
搜索与回溯算法
1 二叉树中和为某一值的路径
1. 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 LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
Deque<Integer> t = new LinkedList<>();
dfs(root, target, 0,t);
return res;
}
public int dfs(TreeNode root, int target,int sum,Deque<Integer> t){
if(root == null) return 0;
t.offer(root.val);
sum+=root.val;
// System.out.println("t: "+t);
if(root.right == null && root.left == null) {
// System.out.println("sum "+sum);
if(sum == target){
res.add(new LinkedList<>(t));
}
}
if(0 != dfs(root.left, target,sum,t))
t.removeLast();
if(0 != dfs(root.right, target,sum,t))
t.removeLast();
return 1;
}
}
2. 优化
package jzof.Day15;
import jzof.TreeNode;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
/**
* @author ahan
* @create_time 2021-11-15-7:21 下午
* 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
*
* 叶子节点 是指没有子节点的节点。
*
*/
public class _34 {
public static void main(String[] args) {
TreeNode head = new TreeNode(5);
TreeNode node1 = new TreeNode(4);
TreeNode node2 = new TreeNode(8);
TreeNode node3 = new TreeNode(11);
TreeNode node4 = new TreeNode(13);
TreeNode node5 = new TreeNode(4);
TreeNode node6 = new TreeNode(7);
TreeNode node7 = new TreeNode(2);
TreeNode node8 = new TreeNode(5);
TreeNode node9 = new TreeNode(1);
head.left = node1;
head.right = node2;
node1.left = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
node3.right = node7;
node5.left = node8;
node5.right = node9;
List<List<Integer>> lists = new _34().pathSum(head, 22);
System.out.println(lists);
}
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
Deque<Integer> temp = new LinkedList<>();
dfs(root, target,temp);
return res;
}
void dfs(TreeNode cur, int sum, Deque<Integer> temp){
if(cur == null) return ;
temp.add(cur.val);
sum -= cur.val;
System.out.println(temp);
if(cur.left == null && cur.right == null && 0 == sum)
res.add(new LinkedList<>(temp));
dfs(cur.left, sum,temp);
dfs(cur.right, sum,temp);
temp.removeLast();
}
}
2 二叉搜索树与双向链表
想到了用中序遍历，还是写的很粗糙，没有用dfs实现，发现使用类变量保存递归过程的上一次递归中结果很有用！
1. 中序遍历
/*
// 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 {
public Node treeToDoublyList(Node root) {
if(root==null)
return null;
Deque<Node> stack = new LinkedList<>();
Deque<Node> res = new LinkedList<>();
Node head ;
Node curNode = root;
Node preNode ;
while(curNode!=null || !stack.isEmpty()){
while(curNode!=null){
stack.push(curNode);
curNode = curNode.left;
}
curNode = stack.pop();
res.offer(curNode);
// System.out.println("curNode: "+curNode+" val: "+curNode.val+" left: "+curNode.left+" right: "+curNode.right);
curNode = curNode.right;
}
// System.out.println(res);
preNode = res.poll();
head = preNode;
curNode = head;
while (!res.isEmpty()){
curNode = res.poll();
preNode.right = curNode;
curNode.left = preNode;
preNode = curNode;
}
// System.out.println(curNode);
head.left = curNode;
curNode.right = head;
return head;
}
}2. DFS
解题思路：
二叉搜索树的中序遍历为 递增序列 ，所以转换成一个 “排序的循环双向链表” ，其中包含三个要素：
- 排序链表： 节点应从小到大排序，因此应使用 中序遍历 “从小到大”访问树的节点。
-
双向链表： 在构建相邻节点的引用关系时，设前驱节点
pre和当前节点cur，不仅应构建pre.right = cur，也应构建cur.left = pre。 -
循环链表： 设链表头节点
head和尾节点tail，则应构建head.left = tail和tail.right = head。
算法流程：
dfs(cur): 递归法中序遍历；
-
终止条件： 当节点
cur为空，代表越过叶节点，直接返回； -
递归左子树，即
dfs(cur.left)； -
构建链表：
-
当
pre为空时： 代表正在访问链表头节点，记为head； -
当
pre不为空时： 修改双向节点引用，即pre.right=cur，cur.left = pre； -
保存
cur： 更新pre = cur，即节点cur是后继节点的pre；
-
当
-
递归右子树，即
dfs(cur.right)； -
特例处理： 若节点
root为空，则直接返回； -
初始化： 空节点
pre； -
转化为双向链表： 调用
dfs(root)； -
构建循环链表： 中序遍历完成后，
head指向头节点，pre指向尾节点，因此修改head和pre的双向节点引用即可； -
返回值： 返回链表的头节点
head即可；
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;
}
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 二叉搜索树的第k大节点
本文解法基于此性质：二叉搜索树的中序遍历为 递增序列 。
因此， “二叉搜索树第 k 大的节点” 可转化为求 “此树的中序遍历倒序的第 k 个节点”。
递归解析：
- 终止条件： 当节点 root 为空（越过叶节点），则直接返回；
- 递归右子树： 即 dfs(root.right)；
-
三项工作：
- 提前返回： 若 k = 0 ，代表已找到目标节点，无需继续遍历，因此直接返回；
- 统计序号： 执行 k = k - 1 （即从 k 减至 0 ）；
- 记录结果： 若 k = 0，代表当前节点为第 k 大的节点，因此记录 res = root.val；
- 递归左子树： 即 dfs(root.left)；
1. 递归+中序遍历
跑完全部节点再查找中序遍历的第size()-k个节点
/**
* 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) {
Deque<TreeNode> stack = new LinkedList<>();
Deque<Integer> res = new LinkedList<>();
TreeNode curNode = root;
while(curNode != null || !stack.isEmpty()){
while(curNode != null){
stack.push(curNode);
curNode = curNode.left;
}
curNode = stack.pop();
res.offer(curNode.val);
curNode = curNode.right;
}
return (int) res.stream().sorted().toArray()[res.size() - k];
}
}public class Solution {
private static List<Integer> arr=new ArrayList<>();
public int kthLargest(TreeNode root, int k) {
//中序遍历,正序赋值数组
inOrder(root);
//寻找第k大的数，输出
return arr.get(arr.size()-k);
}
//中序遍历
private static void inOrder(TreeNode root){
if(root==null)
return;
inOrder(root.left);
arr.add(root.val);
inOrder(root.right);
}
}2. 递归+中序遍历倒序
class Solution {
int res, k;
public int kthLargest(TreeNode root, int k) {
this.k = k;
dfs(root);
return res;
}
void dfs(TreeNode root) {
if(root == null) return;
dfs(root.right);
if(k == 0) return;
if(--k == 0) res = root.val;
dfs(root.left);
}
} 利用类变量维护数值，挺好~
复杂度分析：
- 时间复杂度 O(N)： 当树退化为链表时（全部为右子节点），无论 k 的值大小，递归深度都为 N ，占用 O(N) 时间。
- 空间复杂度 O(N)： 当树退化为链表时（全部为右子节点），系统使用 O(N) 大小的栈空间。