八、树
1、基础知识
树的定义
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;
}BFS
public List<Integer> bfs(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
if (root != null) queue.offer(root);
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
result.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return result;
}二叉树DFS
（各有两种方法：递归+栈）
中序遍历
//中序遍历-递归
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> nodes = new LinkedList<>();
dfs(root, nodes);
return nodes;
}
private void dfs(TreeNode root, List<Integer> nodes) {
if (root != null) {
dfs(root.left, nodes);
nodes.add(root.val);
dfs(root.right, nodes);
}
}
//中序遍历-栈
public List<Integer> inorderTraversal2(TreeNode root) {
List<Integer> nodes = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
nodes.add(curr.val);
curr = curr.right;
}
return nodes;
}前序遍历
//前序遍历-栈
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> nodes = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
//注意差别
nodes.add(curr.val);//!!!!!!!!!!!!!!!!!!!!!!!!
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
// nodes.add(curr.val);
curr = curr.right;
}
return nodes;
}后序遍历
2、基本题型
二叉树DFS
剑指 Offer II 047. 二叉树剪枝 后序遍历递归
public TreeNode pruneTree(TreeNode root) {
if (root == null) {
return null;
}
//后序遍历
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
if (root.left == null && root.right == null && root.val == 0) {
return null;
}
return root;
}/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "#";
}
String leftStr = serialize(root.left);
String rightStr = serialize(root.right);
return String.valueOf(root.val) + "," + leftStr + "," + rightStr;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] nodeStrs = data.split(",");
int[] i = {0};
return dfs(nodeStrs, i);
}
private TreeNode dfs(String[] strs, int[] i){
String str = strs[i[0]];
i[0]++;
if(str.equals("#")){
return null;
}
TreeNode node = new TreeNode(Integer.valueOf(str));
node.left = dfs(strs,i);
node.right = dfs(strs,i);
return node;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));剑指 Offer II 049. 从根节点到叶节点的路径数字之和
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
private int dfs(TreeNode root, int path) {
if (root == null) return 0;
path = path * 10 + root.val;
if (root.left == null && root.right == null) {
return path;
}
return dfs(root.left, path) + dfs(root.right, path);
}剑指 Offer II 050. 向下的路径节点之和 前缀和+递归+回溯（+1递归后需要-1）
private int dfs(TreeNode root, int sum, Map<Integer, Integer> map, int path) {
if (root == null) {
return 0;
}
path += root.val;
int count = map.getOrDefault(path - sum, 0);
map.put(path, map.getOrDefault(path, 0) + 1);
count += dfs(root.left, sum, map, path);
count += dfs(root.right, sum, map, path);
map.put(path, map.get(path) - 1);
return count;
}class Solution {
public int maxPathSum(TreeNode root) {
int[] maxSum = {Integer.MIN_VALUE};
dfs(root, maxSum);
return maxSum[0];
}
private int dfs(TreeNode root, int[] maxSum) {
if (root == null) return 0;
int[] maxSumLeft = {Integer.MIN_VALUE};
int left = Math.max(0, dfs(root.left, maxSumLeft));
int[] maxSumRight = {Integer.MIN_VALUE};
int right = Math.max(0, dfs(root.right, maxSumRight));
maxSum[0] = Math.max(maxSumLeft[0], maxSumRight[0]);
maxSum[0] = Math.max(maxSum[0], root.val + left + right);
return root.val + Math.max(left, right);
}
}二叉搜索树
中序遍历（栈）
剑指 Offer II 055. 二叉搜索树迭代器 （curr + stack）
TreeSet和TreeMap
TreeSet: set.floor(num) <= set.upper(num) >=
剑指 Offer II 057. 值和下标之差都在给定的范围内
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet<Long> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
//在i-k~i的范围内找到小于等于nums[i]的最大的数，检验差值是否符合要求
Long lower = set.floor((long) nums[i]);
if (lower != null && lower >= (long) nums[i] - t) {
return true;
}
//在i-k~i的范围内找到小于等于nums[i]的最大的数，检验差值是否符合要求
Long upper = set.ceiling((long) nums[i]);
if (upper != null && upper <= (long) nums[i] + t) {
return true;
}
//都没有的话，就把数添加到集合里
set.add((long) nums[i]);
//把<=i - k 的都删掉
if (i >= k) {
set.remove((long) nums[i - k]);
}
}
return false;
}
}TreeMap
Map.Entry<Integer, Integer> event = events.floorEntry(start);class MyCalendar {
private TreeMap<Integer, Integer> events;
public MyCalendar() {
events = new TreeMap<Integer, Integer>();
}
public boolean book(int start, int end) {
Integer lStart = events.floorKey(start);
if (lStart != null && events.get(lStart) > start) {
return false;
}
Integer rStart = events.ceilingKey(start);
if (rStart != null && rStart < end) {
return false;
}
events.put(start, end);
return true;
}
}
版权声明：本文为qq_37039382原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。