算法-二叉树算法总结
2022-01-03 本文已影响0人
攻城老狮
二叉树算法总结
1 二叉树的遍历
1.1 前序遍历
- 递归
// 144. 二叉树的前序遍历
// 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
preOrder(root,res);
return res;
}
private void preOrder(TreeNode root,List<Integer> res) {
if (root == null) return;
res.add(root.val);
preOrder(root.left,res);
preOrder(root.right,res);
}
}
- 迭代
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode tmpNode = stack.pop();
res.add(tmpNode.val);
if (tmpNode.right != null) stack.push(tmpNode.right);
if (tmpNode.left != null) stack.push(tmpNode.left);
}
return res;
}
}
1.2 中序遍历
- 递归
// 94. 二叉树的中序遍历
// 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inOrder(root,res);
return res;
}
private void inOrder(TreeNode root,List<Integer> res) {
if (root == null) return;
inOrder(root.left,res);
res.add(root.val);
inOrder(root.right,res);
}
}
- 迭代
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
}
return res;
}
}
1.3 后序遍历
- 递归
// 145. 二叉树的后序遍历
// 给定一个二叉树，返回它的 后序 遍历。
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postOrder(root,res);
return res;
}
private void postOrder(TreeNode root,List<Integer> res) {
if (root == null) return;
postOrder(root.left,res);
postOrder(root.right,res);
res.add(root.val);
}
}
- 迭代
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode tmpNode = stack.pop();
res.add(tmpNode.val);
if (tmpNode.left != null) stack.push(tmpNode.left);
if (tmpNode.right != null) stack.push(tmpNode.right);
}
Collections.reverse(res);
return res;
}
}
1.4 层序遍历
// 102. 二叉树的层序遍历
// 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int len = queue.size();
List<Integer> tmpList = new ArrayList<>();
for (int i = 0; i < len; i++) {
TreeNode tmpNode = queue.poll();
tmpList.add(tmpNode.val);
if (tmpNode.left != null) queue.offer(tmpNode.left);
if (tmpNode.right != null) queue.offer(tmpNode.right);
}
res.add(tmpList);
}
return res;
}
}
2 二叉树的属性
思路：
- 如果需要搜索整颗二叉树且不用处理递归返回值，递归函数就不要返回值。113
- 如果需要搜索整颗二叉树且需要处理递归返回值，递归函数就需要返回值。 236
- 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。112
// DFS 后序遍历
// 101. 对称二叉树
// 给定一个二叉树，检查它是否是镜像对称的。
class Solution {
public boolean isSymmetric(TreeNode root) {
return compare(root.left,root.right);
}
private boolean compare (TreeNode left, TreeNode right) {
if (left == null && right != null) return false;
if (left != null && right == null) return false;
if (left == null && right == null) return true;
if (left.val != right.val) return false;
boolean outFlag = compare(left.left,right.right);
boolean inFlag = compare(left.right,right.left);
return outFlag && inFlag;
}
}
// DFS 后序遍历
// 104. 二叉树的最大深度
// 给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
class Solution {
public int maxDepth(TreeNode root) {
return getDepth(root);
}
private int getDepth(TreeNode root) {
if (root == null) return 0;
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
return 1 + Math.max(leftDepth,rightDepth);
}
}
// DFS 后序遍历
// 559. N 叉树的最大深度
// 给定一个 N 叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
class Solution {
public int maxDepth(Node root) {
if (root == null) return 0;
int maxDepth = 0;
for (int i = 0 ; i < root.children.size(); i++) {
int deep = maxDepth(root.children.get(i));
maxDepth = Math.max(maxDepth,deep);
}
return 1 + maxDepth;
}
}
// DFS 后序遍历
// 111. 二叉树的最小深度
// 给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
class Solution {
public int minDepth(TreeNode root) {
return getDepth(root);
}
private int getDepth(TreeNode root) {
if (root == null) return 0;
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
if (root.left == null && root.right != null) {
return 1 + rightDepth;
} else if (root.left != null && root.right == null) {
return 1 + leftDepth;
} else {
return 1 + Math.min(leftDepth,rightDepth);
}
}
}
// DFS 后序遍历
// 222. 完全二叉树的节点个数
// 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
class Solution {
public int countNodes(TreeNode root) {
if (root == null) return 0;
int leftNum = countNodes(root.left);
int rightNum = countNodes(root.right);
return 1 + leftNum + rightNum;
}
}
// DFS 后序遍历
// 110. 平衡二叉树
// 给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root) == -1 ? false : true;
}
private int getHeight(TreeNode root) {
if (root == null) return 0;
int leftHeight = getHeight(root.left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = getHeight(root.right);
if (rightHeight == -1) {
return -1;
}
return Math.abs(leftHeight - rightHeight) > 1 ? -1 : 1 + Math.max(leftHeight,rightHeight);
}
}
// DFS 前序遍历
// 257. 二叉树的所有路径
// 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
class Solution {
List<String> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
if (root == null) return res;
path.add(root.val);
traversal(root);
return res;
}
private void traversal(TreeNode root) {
if (root.left == null && root.right == null) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < path.size() - 1; i++) {
sb.append(path.get(i) + "->");
}
sb.append(path.get(path.size() - 1));
res.add(sb.toString());
}
if (root.left != null) {
path.add(root.left.val);
traversal(root.left);
path.remove(path.size() - 1);
}
if (root.right != null) {
path.add(root.right.val);
traversal(root.right);
path.remove(path.size() - 1);
}
}
}
// DFS 后序遍历
// 404. 左叶子之和
// 计算给定二叉树的所有左叶子之和。
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
int leftValue = sumOfLeftLeaves(root.left);
int rightValue = sumOfLeftLeaves(root.right);
int midValue = 0;
if (root.left != null && root.left.left == null && root.left.right == null) {
midValue = root.left.val;
}
return leftValue + rightValue + midValue;
}
}
// DFS 前序遍历
// 513. 找树左下角的值
// 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。
class Solution {
private int maxDeep;
private int maxVal;
public int findBottomLeftValue(TreeNode root) {
maxVal = root.val;
maxDeep = 0;
travesal(root,0);
return maxVal;
}
private void travesal(TreeNode root,int tmpDeep) {
if (root == null) return;
if (root.left == null && root.right == null) {
if (tmpDeep > maxDeep) {
maxDeep = tmpDeep;
maxVal = root.val;
}
}
travesal(root.left,tmpDeep + 1); //隐式回溯
travesal(root.right,tmpDeep + 1);
}
}
// DFS 前序遍历（中节点没有逻辑）
// 112. 路径总和
// 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
return traversal(root,targetSum - root.val);
}
private boolean traversal(TreeNode root, int tmpSum) {
if (root.left == null && root.right == null && tmpSum == 0) return true;
if (root.left == null && root.right == null) return false;
if (root.left != null) {
if (traversal(root.left,tmpSum - root.left.val)) return true;
}
if (root.right != null) {
if (traversal(root.right,tmpSum - root.right.val)) return true;
}
return false;
}
}
// DFS 前序遍历
// 113. 路径总和 II
// 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null) return res;
path.add(root.val);
traversal(root,targetSum - root.val);
return res;
}
private void traversal(TreeNode root, int tmpNum) {
if (root.left == null && root.right == null && tmpNum == 0) {
res.add(new ArrayList<>(path));
return;
}
if (root.left == null && root.right == null) return;
if (root.left != null) {
path.add(root.left.val);
tmpNum -= root.left.val;
traversal(root.left,tmpNum);
tmpNum += root.left.val;
path.remove(path.size() - 1);
}
if (root.right != null) {
path.add(root.right.val);
tmpNum -= root.right.val;
traversal(root.right,tmpNum);
tmpNum += root.right.val;
path.remove(path.size() - 1);
}
}
}
// 后序遍历
// 剑指 Offer II 047. 二叉树剪枝
// 给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。节点 node 的子树为 node 本身，以及所有 node 的后代。
class Solution {
public TreeNode pruneTree(TreeNode root) {
if (root == null) return null;
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
if (root.val == 0 && root.left == null && root.right == null) {
return null;
}
return root;
}
}
// 前序遍历
// 剑指 Offer II 048. 序列化与反序列化二叉树
// 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "null";
return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}
// Decodes your encoded data to tree.
private int i = 0;
public TreeNode deserialize(String data) {
String[] strs = data.split(",");
TreeNode root = traversal(strs);
return root;
}
private TreeNode traversal(String[] strs) {
String str = strs[i];
i++;
if ("null".equals(str)) {
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(str));
root.left = traversal(strs);
root.right = traversal(strs);
return root;
}
}
// 前序遍历 前序处理节点处理个寂寞即可
// 剑指 Offer II 049. 从根节点到叶节点的路径数字之和
// 给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字：例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。计算从根节点到叶节点生成的 所有数字之和 。叶节点 是指没有子节点的节点。
class Solution {
private int res = 0;
public int sumNumbers(TreeNode root) {
if (root == null) return res;
traversal(root,root.val);
return res;
}
private void traversal(TreeNode root,int path) {
if (root.left == null && root.right == null) {
res += path;
return;
}
if (root.left != null) {
traversal(root.left,path * 10 + root.left.val);
}
if (root.right != null) {
traversal(root.right,path * 10 + root.right.val);
}
}
}
// 前序遍历
// 剑指 Offer II 050. 向下的路径节点之和
// 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
class Solution {
public int pathSum(TreeNode root, int targetSum) {
Map<Integer,Integer> map = new HashMap<>();
map.put(0,1);
return traversal(root,targetSum,0,map);
}
private int traversal(TreeNode root,int target,int sum,Map<Integer,Integer> map) {
if (root == null) return 0;
sum += root.val;
int count = map.getOrDefault(sum - target,0);
map.put(sum,map.getOrDefault(sum,0) + 1);
count += traversal(root.left,target,sum,map);
count += traversal(root.right,target,sum,map);
map.put(sum,map.get(sum) - 1);
return count;
}
}
// 后序遍历
// 剑指 Offer II 051. 节点之和最大的路径
// 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。
class Solution {
private int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
traversal(root,null);
return res;
}
private int traversal(TreeNode root,TreeNode parent) {
if (root == null) return 0;
int leftSum = traversal(root.left,root);
int rightSum = traversal(root.right,root);
int sumWithRoot = Math.max(leftSum + root.val + rightSum,Math.max(leftSum + root.val,Math.max(root.val + rightSum, root.val)));
if (root.left == null && root.right == null) {
res = Math.max(res,sumWithRoot);
} else if (root.left != null && root.right == null) {
res = Math.max(res,Math.max(sumWithRoot,leftSum));
} else if (root.left == null && root.right != null) {
res = Math.max(res,Math.max(sumWithRoot,rightSum));
} else {
res = Math.max(res,Math.max(sumWithRoot,Math.max(leftSum,rightSum)));
}
// 非根节点，不能考虑返回经过头节点的路径
if (parent != null) {
return Math.max(leftSum + root.val,Math.max(root.val + rightSum,root.val));
}
// 根节点
return sumWithRoot;
}
}
3 二叉树的修改与构造
// DFS 前序遍历
// 226. 翻转二叉树
// 翻转一棵二叉树。
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
swap(root);
invertTree(root.left);
invertTree(root.right);
return root;
}
private void swap(TreeNode root) {
TreeNode tmpNode = root.left;
root.left = root.right;
root.right = tmpNode;
}
}
// 106. 从中序与后序遍历序列构造二叉树
// 根据一棵树的中序遍历与后序遍历构造二叉树。
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTree(inorder,0,inorder.length,postorder,0,postorder.length);
}
private TreeNode buildTree(int[] inorder,int inLeft,int inRight,int[] postorder,int postLeft,int postRight) {
if (inRight - inLeft < 1) return null;
int rootVal = postorder[postRight - 1];
TreeNode root = new TreeNode(rootVal);
int rootIndex = 0;
for (int i = inLeft; i < inRight; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
// 根据rootIndex划分左右子树
root.left = buildTree(inorder,inLeft,rootIndex,postorder,postLeft,postLeft + (rootIndex - inLeft));
root.right = buildTree(inorder,rootIndex + 1,inRight,postorder,postLeft + (rootIndex - inLeft),postRight - 1);
return root;
}
}
// DFS 前序遍历
// 105. 从前序与中序遍历序列构造二叉树
// 给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder,0,preorder.length,inorder,0,inorder.length);
}
private TreeNode buildTree(int[] preorder,int preLeft,int preRight,int[] inorder,int inLeft,int inRight) {
if (inRight - inLeft < 1) return null;
int rootVal = preorder[preLeft];
TreeNode root = new TreeNode(rootVal);
int rootIndex = 0;
for (int i = inLeft; i < inRight; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
root.left = buildTree(preorder,preLeft + 1,preLeft + 1 + (rootIndex - inLeft),inorder,inLeft,rootIndex);
root.right = buildTree(preorder,preLeft + 1 + (rootIndex - inLeft),preRight,inorder,rootIndex + 1,inRight);
return root;
}
}
// DFS 前序遍历
// 654. 最大二叉树
// 给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：二叉树的根是数组 nums 中的最大元素。左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。返回有给定数组 nums 构建的 最大二叉树 。
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return constructMaximumBinaryTree(nums,0,nums.length);
}
private TreeNode constructMaximumBinaryTree(int[] nums,int preLeft,int preRight) {
if (preRight - preLeft < 1) return null;
// 初始赋值
int maxValue = nums[preLeft];
int maxIndex = preLeft;
for (int i = preLeft + 1; i < preRight; i++) {
if (nums[i] > maxValue) {
maxValue = nums[i];
maxIndex = i;
}
}
TreeNode root = new TreeNode(maxValue);
root.left = constructMaximumBinaryTree(nums,preLeft,maxIndex);
root.right = constructMaximumBinaryTree(nums,maxIndex + 1,preRight);
return root;
}
}
// DFS 前序遍历
// 617. 合并二叉树
// 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
root1.val += root2.val;
root1.left = mergeTrees(root1.left,root2.left);
root1.right = mergeTrees(root1.right,root2.right);
return root1;
}
}
4 二叉搜索树
思路：
- 二叉搜索树是一个有序树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉搜索树
- 中序遍历下，输出的二叉搜索树节点的数值是有序序列。
// DFS 搜索遍历 找到结果直接return
// 700. 二叉搜索树中的搜索
// 给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) return root;
if (root.val > val) return searchBST(root.left,val);
if (root.val < val) return searchBST(root.right,val);
return null;
}
}
// DFS 中序遍历 找到结果直接return
// 98. 验证二叉搜索树
// 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。
class Solution {
private long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (!isValidBST(root.left)) return false;
if (root.val <= pre) return false;
pre = root.val;
return isValidBST(root.right);
}
}
// DFS 中序遍历
// 530. 二叉搜索树的最小绝对差
// 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。差值是一个正数，其数值等于两值之差的绝对值。
class Solution {
private TreeNode pre;
private int diff = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if (root == null) return 0;
traversal(root);
return diff;
}
private void traversal(TreeNode root) {
if (root == null) return;
traversal(root.left);
if (pre != null) {
diff = Math.min(diff,root.val - pre.val);
}
pre = root;
traversal(root.right);
}
}
// DFS 中序遍历
// 501. 二叉搜索树中的众数
// 给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
class Solution {
private List<Integer> resList = new ArrayList<>();
private TreeNode pre;
private int maxCount = 0;
private int count = 0;
public int[] findMode(TreeNode root) {
traversal(root);
int[] res = new int[resList.size()];
for (int i = 0; i < res.length; i++) {
res[i] = resList.get(i);
}
return res;
}
private void traversal(TreeNode root) {
if (root == null) return;
traversal(root.left);
if (pre == null || root.val != pre.val) {
count = 1;
} else {
count++;
}
if (count > maxCount) {
maxCount = count;
resList.clear();
resList.add(root.val);
} else if (count == maxCount) {
resList.add(root.val);
}
pre = root;
traversal(root.right);
}
}
// DFS 中序遍历变种
// 538. 把二叉搜索树转换为累加树
// 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
class Solution {
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
traversal(root);
return root;
}
private void traversal(TreeNode root) {
if (root == null) return;
traversal(root.right);
sum += root.val;
root.val = sum;
traversal(root.left);
}
}
// 中序遍历
// 剑指 Offer II 052. 展平二叉搜索树
// 给你一棵二叉搜索树，请 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
class Solution {
private TreeNode preNode;
public TreeNode increasingBST(TreeNode root) {
TreeNode dummy = new TreeNode(-1);
preNode = dummy;
traversal(root);
return dummy.right;
}
private void traversal(TreeNode root) {
if (root == null) return;
traversal(root.left);
preNode.right = root;
root.left = null;
preNode = root;
traversal(root.right);
}
}
// 中序遍历
// 剑指 Offer II 053. 二叉搜索树中的中序后继
// 给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。
class Solution {
private boolean flag;
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
return traversal(root,p);
}
private TreeNode traversal(TreeNode root,TreeNode p) {
if (root == null) return null;
TreeNode node = traversal(root.left,p);
if (node != null) return node;
if (flag) {
return root;
} else if (root.val == p.val) {
flag = true;
}
return traversal(root.right,p);
}
}
// 中序遍历
// 剑指 Offer II 054. 所有大于等于节点的值之和
// 给定一个二叉搜索树，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
class Solution {
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
traversal(root);
return root;
}
private void traversal(TreeNode root) {
if (root == null) return;
traversal(root.right);
sum += root.val;
root.val = sum;
traversal(root.left);
}
}
// 中序遍历
// 剑指 Offer II 055. 二叉搜索树迭代器
// 实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。int next()将指针向右移动，然后返回指针处的数字。注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
class BSTIterator {
private TreeNode root;
private TreeNode preNode;
public BSTIterator(TreeNode root) {
TreeNode dummy = new TreeNode(-1);
preNode = dummy;
traversal(root);
this.root = dummy.right;
}
private void traversal(TreeNode root) {
if (root == null) return;
traversal(root.left);
preNode.right = root;
root.left = null;
preNode = root;
traversal(root.right);
}
public int next() {
int val = root.val;
root = root.right;
return val;
}
public boolean hasNext() {
return root == null ? false : true;
}
}
// 中序遍历
// 剑指 Offer II 056. 二叉搜索树中两个节点之和
// 给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。
class Solution {
private Map<Integer,Integer> map = new HashMap<>();
public boolean findTarget(TreeNode root, int k) {
return traversal(root,k);
}
private boolean traversal(TreeNode root,int k) {
if (root == null) return false;
if(traversal(root.left,k)) return true;
if (map.containsKey(k - root.val)) {
return true;
}
map.put(root.val,1);
return traversal(root.right,k);
}
}
5 二叉树的公共祖先问题
思路 ：
- 求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从低向上的遍历方式。
- 在回溯的过程中，必然要遍历整颗二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
// DFS 后序遍历
// 本题函数有返回值，是因为回溯的过程需要递归函数的返回值做判断，但本题我们依然要遍历树的所有节点。递归函数有返回值就是要遍历某一条边，但有返回值也要看如何处理返回值。如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树呢？
// 搜索一条边的写法：
// if (递归函数(root->left)) return ;
// if (递归函数(root->right)) return ;
// 搜索整个树写法：
// left = 递归函数(root->left);
// right = 递归函数(root->right);
// left与right的逻辑处理;
// 在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）。
// 236. 二叉树的最近公共祖先
// 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return traversal(root,p,q);
}
private TreeNode traversal(TreeNode root,TreeNode p,TreeNode q) {
if (root == p || root == q || root == null) return root;
TreeNode leftNode = traversal(root.left,p,q);
TreeNode rightNode = traversal(root.right,p,q);
if (leftNode != null && rightNode != null) {
return root;
} else if (leftNode == null && rightNode != null) {
return rightNode;
} else if (leftNode != null && rightNode == null) {
return leftNode;
} else {
return null;
}
}
}
// DFS 前序遍历（节点无处理逻辑）
// 和二叉树：公共祖先问题不同，普通二叉树求最近公共祖先需要使用回溯，从底向上来查找，二叉搜索树就不用了，因为搜索树有序（相当于自带方向），那么只要从上向下遍历就可以了。
// 235. 二叉搜索树的最近公共祖先
// 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return traversal(root,p,q);
}
private TreeNode traversal(TreeNode root,TreeNode p,TreeNode q) {
if (root == null) return null;
if (root.val > p.val && root.val > q.val) {
TreeNode leftNode = traversal(root.left,p,q);
if (leftNode != null) return leftNode;
}
if (root.val < p.val && root.val < q.val) {
TreeNode rightNode = traversal(root.right,p,q);
if (rightNode != null) return rightNode;
}
return root;
}
}
6 二叉搜索树的修改与构造
// DFS 搜索遍历
// 有返回值的话，可以利用返回值完成新加入的节点与其父节点的赋值操作
// 701. 二叉搜索树中的插入操作
// 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
TreeNode node = new TreeNode(val);
return node;
}
if (root.val > val) root.left = insertIntoBST(root.left,val);
if (root.val < val) root.right = insertIntoBST(root.right,val);
return root;
}
}
// DFS 搜索遍历
// 有以下五种情况：
// 第一种情况：
// 没找到删除的节点，遍历到空节点直接返回了
// 找到删除的节点:
// 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
// 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
// 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
// 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
// 450. 删除二叉搜索树中的节点
// 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (root.val == key) {
if (root.left == null && root.right == null) {
return null;
} else if (root.left != null && root.right == null) {
return root.left;
} else if (root.left == null && root.right != null) {
return root.right;
} else {
TreeNode cur = root.right;
while (cur.left != null) {
cur = cur.left;
}
cur.left = root.left;
return root.right;
}
}
if (root.val > key) root.left = deleteNode(root.left,key);
if (root.val < key) root.right = deleteNode(root.right,key);
return root;
}
}
// DFS 搜索遍历
// 因为是要遍历整棵树，做修改，其实不需要返回值也可以，我们也可以完成修剪（其实就是从二叉树中移除节点）的操作。但是有返回值，更方便，可以通过递归函数的返回值来移除节点。
// 669. 修剪二叉搜索树
// 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) return null;
if (root.val < low) {
TreeNode rightNode = trimBST(root.right,low,high);
return rightNode;
}
if (root.val > high) {
TreeNode leftNode = trimBST(root.left,low,high);
return leftNode;
}
root.left = trimBST(root.left,low,high);
root.right = trimBST(root.right,low,high);
return root;
}
}
// DFS 前序遍历
// 108. 将有序数组转换为二叉搜索树
// 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return traversal(nums,0,nums.length - 1); // [left,right]
}
private TreeNode traversal(int[] nums,int left,int right) {
if (left > right) return null;
int mid = left + ((right - left) >> 1);
TreeNode root = new TreeNode(nums[mid]);
root.left = traversal(nums,left,mid - 1);
root.right = traversal(nums,mid + 1,right);
return root;
}
}
7 TreeSet 与 TreeMap
// 剑指 Offer II 057. 值和下标之差都在给定的范围内
// 给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。如果存在则返回 true，不存在返回 false。
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet<Long> treeSet = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
Long lower = treeSet.floor((long)nums[i]);
if (lower != null && lower >= (long)nums[i] - t) {
return true;
}
Long higher = treeSet.ceiling((long)nums[i]);
if (higher != null && higher <= (long)nums[i] + t) {
return true;
}
treeSet.add((long)nums[i]);
if (i >= k) {
treeSet.remove((long)nums[i - k]);
}
}
return false;
}
}
// 剑指 Offer II 058. 日程表
// 请实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排，则可以存储这个新的日程安排。
class MyCalendar {
private TreeMap<Integer,Integer> treeMap = new TreeMap<>();
public MyCalendar() {
}
public boolean book(int start, int end) {
Map.Entry<Integer,Integer> entry = treeMap.floorEntry(start);
if (entry != null && entry.getValue() > start) return false;
entry = treeMap.ceilingEntry(start);
if (entry != null && entry.getKey() < end) return false;
treeMap.put(start,end);
return true;
}
}
8 堆相关
// 剑指 Offer II 059. 数据流的第 K 大数值
// 设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。请实现 KthLargest 类：KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
class KthLargest {
private Queue<Integer> queue;
private int size;
public KthLargest(int k, int[] nums) {
queue = new PriorityQueue<>();
size = k;
for (int i = 0; i < nums.length; i++) {
add(nums[i]);
}
}
public int add(int val) {
if (queue.size() < size) {
queue.offer(val);
} else if (queue.peek() < val) {
queue.poll();
queue.offer(val);
}
return queue.peek();
}
}
// 剑指 Offer II 060. 出现频率最高的 k 个数字
// 给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元素。可以按 任意顺序 返回答案。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num,map.getOrDefault(num,0) + 1);
}
Queue<Map.Entry<Integer,Integer>> queue = new PriorityQueue<>((e1,e2)->{
return e1.getValue() - e2.getValue();
});
for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
if (queue.size() < k) {
queue.offer(entry);
} else if (queue.peek().getValue() < entry.getValue()) {
queue.poll();
queue.offer(entry);
}
}
int[] res = new int[k];
int index = 0;
for(Map.Entry<Integer,Integer> entry : queue) {
res[index++] = entry.getKey();
}
return res;
}
}
// 剑指 Offer II 061. 和最小的 k 个数对
// 给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk) 。
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> res = new ArrayList<>();
Queue<int[]> queue = new PriorityQueue<>((p1,p2)->{
return (p2[0] + p2[1]) - (p1[0] + p1[1]);
});
for (int i = 0; i < Math.min(nums1.length,k); i++) {
for (int j = 0; j < Math.min(nums2.length,k); j++) {
if (queue.size() < k) {
queue.offer(new int[]{nums1[i],nums2[j]});
} else if (queue.peek()[0] + queue.peek()[1] > nums1[i] + nums2[j]) {
queue.poll();
queue.offer(new int[]{nums1[i],nums2[j]});
}
}
}
for (int[] p : queue) {
res.add(Arrays.asList(p[0],p[1]));
}
return res;
}
}
9 前缀树
// 剑指 Offer II 062. 实现前缀树
// Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
class Trie {
public static class TrieNode {
public TrieNode[] children;
public boolean isWord;
public TrieNode() {
children = new TrieNode[26];
isWord = false;
}
}
public TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode cur = root;
for (char ch : word.toCharArray()) {
if (cur.children[ch - 'a'] == null) {
cur.children[ch - 'a'] = new TrieNode();
}
cur = cur.children[ch - 'a'];
}
cur.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode cur = root;
for (char ch : word.toCharArray()) {
if (cur.children[ch - 'a'] == null) {
return false;
}
cur = cur.children[ch - 'a'];
}
return cur.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode cur = root;
for (char ch : prefix.toCharArray()) {
if (cur.children[ch - 'a'] == null) {
return false;
}
cur = cur.children[ch - 'a'];
}
return true;
}
}
// 剑指 Offer II 063. 替换单词
// 在英语中，有一个叫做 词根(root) 的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。现在，给定一个由许多词根组成的词典和一个句子，需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。需要输出替换之后的句子。
class Solution {
public String replaceWords(List<String> dictionary, String sentence) {
TrieNode root = buildTree(dictionary);
String[] strs = sentence.split(" ");
for (int i = 0; i < strs.length; i++) {
String prefix = toPrefix(root,strs[i]);
if (prefix != null) {
strs[i] = prefix;
}
}
return String.join(" ",strs);
}
public static class TrieNode {
public TrieNode[] children;
public boolean isWord;
public TrieNode() {
children = new TrieNode[26];
isWord = false;
}
}
private TrieNode buildTree(List<String> dictionary) {
TrieNode root = new TrieNode();
for (String str : dictionary) {
TrieNode cur = root;
for (char ch : str.toCharArray()) {
if (cur.children[ch - 'a'] == null) {
cur.children[ch - 'a'] = new TrieNode();
}
cur = cur.children[ch - 'a'];
}
cur.isWord = true;
}
return root;
}
private String toPrefix(TrieNode root,String str) {
TrieNode cur = root;
StringBuilder sb = new StringBuilder();
for (char ch : str.toCharArray()) {
if (cur.isWord || cur.children[ch - 'a'] == null) {
break;
}
sb.append(ch);
cur = cur.children[ch - 'a'];
}
if (cur.isWord) {
return sb.toString();
} else {
return null;
}
}
}
// 剑指 Offer II 064. 神奇的字典
// 设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于已构建的神奇字典中。
class MagicDictionary {
public static class TrieNode {
public TrieNode[] children;
public boolean isWord;
public TrieNode() {
children = new TrieNode[26];
isWord = false;
}
}
public TrieNode root;
/** Initialize your data structure here. */
public MagicDictionary() {
root = new TrieNode();
}
public void buildDict(String[] dictionary) {
for (String str : dictionary) {
TrieNode cur = root;
for (char ch : str.toCharArray()) {
if (cur.children[ch - 'a'] == null) {
cur.children[ch - 'a'] = new TrieNode();
}
cur = cur.children[ch - 'a'];
}
cur.isWord = true;
}
}
public boolean search(String searchWord) {
return traversal(root,searchWord,0,0);
}
private boolean traversal(TrieNode root, String word,int len,int num) {
if (root == null) return false;
if (root.isWord && len == word.length() && num == 1) return true;
if (len < word.length() && num <= 1) {
boolean found = false;
for (int i = 0; i < 26 && !found; i++) {
int next = i == word.charAt(len) - 'a' ? num : num + 1;
found = traversal(root.children[i],word,len + 1,next);
}
return found;
}
return false;
}
}
// 剑指 Offer II 065. 最短的单词编码
// 单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：words.length == indices.length助记字符串 s 以 '#' 字符结尾对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等给定一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。
class Solution {
private int res;
public int minimumLengthEncoding(String[] words) {
TrieNode root = buildTree(words);
traversal(root,1);
return res;
}
public static class TrieNode{
private TrieNode[] children;
public TrieNode() {
children = new TrieNode[26];
}
}
private TrieNode buildTree(String[] words) {
TrieNode root = new TrieNode();
for (String str : words) {
TrieNode cur = root;
for (int i = str.length() - 1; i >= 0; i--) {
if (cur.children[str.charAt(i) - 'a'] == null) {
cur.children[str.charAt(i) - 'a'] = new TrieNode();
}
cur = cur.children[str.charAt(i) - 'a'];
}
}
return root;
}
private void traversal(TrieNode root, int len) {
boolean isLeaf = true;
for (int i = 0; i < 26; i++) {
if (root.children[i] != null) {
isLeaf = false;
traversal(root.children[i],len + 1);
}
}
if (isLeaf) {
res += len;
}
}
}
// 剑指 Offer II 066. 单词之和
// 实现一个 MapSum 类，支持两个方法，insert 和 sum：MapSum() 初始化 MapSum 对象void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。
class MapSum {
public static class TrieNode {
public TrieNode[] children;
public int val;
public TrieNode() {
children = new TrieNode[26];
val = 0;
}
}
public TrieNode root;
/** Initialize your data structure here. */
public MapSum() {
root = new TrieNode();
}
public void insert(String key, int val) {
TrieNode cur = root;
for (char ch : key.toCharArray()) {
if (cur.children[ch - 'a'] == null) {
cur.children[ch - 'a'] = new TrieNode();
}
cur = cur.children[ch - 'a'];
}
cur.val = val;
}
public int sum(String prefix) {
TrieNode cur = root;
for (char ch : prefix.toCharArray()) {
if (cur.children[ch - 'a'] == null) {
return 0;
}
cur = cur.children[ch - 'a'];
}
return getSum(cur);
}
private int getSum(TrieNode root) {
if (root == null) return 0;
int sum = root.val;
for (int i = 0; i < 26; i++) {
sum += getSum(root.children[i]);
}
return sum;
}
}
// 剑指 Offer II 067. 最大的异或
// 给定一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
class Solution {
public static class TrieNode {
public TrieNode[] children;
public TrieNode() {
children = new TrieNode[2];
}
}
private TrieNode buildTree(int[] nums) {
TrieNode root = new TrieNode();
for (int num : nums) {
TrieNode cur = root;
for (int i = 31; i >=0; i--) {
int bit = (num >> i) & 1;
if (cur.children[bit] == null) {
cur.children[bit] = new TrieNode();
}
cur = cur.children[bit];
}
}
return root;
}
public int findMaximumXOR(int[] nums) {
TrieNode root = buildTree(nums);
int max = 0;
for (int num : nums) {
TrieNode cur = root;
int xor = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (cur.children[1 - bit] != null) {
xor = (xor << 1) + 1;
cur = cur.children[1 - bit];
} else {
xor = xor << 1;
cur = cur.children[bit];
}
}
max = Math.max(max,xor);
}
return max;
}
}
