二叉树
使用Java实现二叉树:
public class BinaryTree {
public static class Node {
public Node(int val) {
this.val = val;
}
public int val;
public Node left;
public Node right;
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
head.right.right = new Node(7);
}
}
上述的代码转换为二叉树图形如下:
前序遍历、中序遍历、后序遍历
二叉树的遍历分为三种:
前序遍历:头、左、右, 1、2、4、5、3、6、7
中序遍历:左、头、右, 4、2、5、1、6、3、7
后续遍历:左、右、头, 4、5、2、6、7、3、1
这里的前序、后序、中序,针对的目标是头节点,头节点在最前面,就是前序。
使用Java代码实现三种遍历方式:
public static void pre(Node node) {
if (node == null) return;
System.out.print(node.val + " ");
pre(node.left);
pre(node.right);
}
public static void in(Node node) {
if (node == null) return;
in(node.left);
System.out.print(node.val + " ");
in(node.right);
}
public static void pos(Node node) {
if (node == null) return;
pos(node.left);
pos(node.right);
System.out.print(node.val + " ");
}
递归序遍历
前序遍历、中序遍历、后序遍历都是对递归序的改造;使用递归序遍历二叉树,每个节点都会被遍历三次,在前中后三个位置每次都打印即是递归序:
public static void f(Node node) {
if (node == null) return;
// 1
System.out.print(node.val + " ");
f(node.left);
// 2
System.out.print(node.val + " ");
f(node.right);
// 3
System.out.print(node.val + " ");
}
结果为 1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3 1 ,如果只保留每个数字第一次出现的情况,那么就是前序遍历:1 2 4 3 6 7;同理,如果保留第二次出现的情况就是中序遍历;保留最后一次出现的情况,那么就是后序遍历。
比较两颗二叉树结构是否完全相同
对应试题:https://leetcode-cn.com/problems/same-tree/
可以使用递归序遍历比较每个节点:
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null ^ q == null) { // 抑或,相同为0(false) 不同为1(true), p和q有一个为null,一个不为null
return false;
}
if (p == null) { // 如果 p == q == null,代表递归结束
return true;
}
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
判断一颗树是否是镜面树
对应试题:
左右对称的树称为镜面树:
头节点下可以分为左右两个子树,他们相同的一层之间的左子树与对方的右子树相同
Java实现如下:
public boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
public boolean isMirror(TreeNode p, TreeNode q) {
if (p == null ^ q == null) {
return false;
}
if (p == null) {
return true;
}
return p.val == q.val && isMirror(p.left, q.right) && isMirror(p.right, q.left);
}
返回一棵树的最大深度
对应试题:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
从前序与中序遍历序列构造二叉树
对应试题:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length == 0) {
return null;
}
return f(preorder, 0, preorder.length - 1, inorder, 0, preorder.length - 1);
}
private TreeNode f(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2) {
if (l1 > r1) {
return null;
}
if (l1 == r1) {
return new TreeNode(preorder[l1]);
}
int root = preorder[l1];
int find = 0;
while (inorder[find] != root) {
find++;
}
TreeNode rootNode = new TreeNode(root);
rootNode.left = f(preorder, l1 + 1, l1 + find - l2, inorder, l2, find - 1);
rootNode.right = f(preorder, l1 + find - l2 + 1, r1, inorder, find + 1, r2);
return rootNode;
}
二叉树按层遍历并收集节点
对应试题:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
解题思路:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return Collections.emptyList();
}
List<List<Integer>> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
List<TreeNode> ceng = new ArrayList<>();
while (!queue.isEmpty()) {
ceng.add(queue.poll());
}
ceng.forEach(e -> {
if (e.left != null) {
queue.add(e.left);
}
if (e.right != null) {
queue.add(e.right);
}
});
result.add(ceng.stream().map(e -> e.val).toList());
}
return result;
}
}
判断树是否是平衡二叉树
对应leetcode:https://leetcode-cn.com/problems/balanced-binary-tree/
平衡二叉树:在一个二叉树中,每一颗子树的左子树的深度与右子树的深度 <= 1,并且左数是一个平衡二叉树、右树也是一个平衡二叉树。
public boolean isBalanced(TreeNode root) {
return getNodeInfo(root).isBalanced;
}
public Info getNodeInfo(TreeNode node) {
if (node == null) {
return new Info(true, 0);
}
Info leftInfo = getNodeInfo(node.left);
Info rightInfo = getNodeInfo(node.right);
return new Info(
leftInfo.isBalanced && rightInfo.isBalanced && Math.abs(leftInfo.height - rightInfo.height) <= 1,
Math.max(leftInfo.height, rightInfo.height) + 1);
}
static class Info {
public boolean isBalanced; // 是平衡树
public int height; // 树的高度
public Info(boolean isBalanced, int height) {
this.isBalanced = isBalanced;
this.heig
ht = height;
}
}
判断树是否是搜索二叉树
在一个树中,每一颗子树的左树的值都比当前值小,右树的值都比当前值大。
判断一个二叉树是否是搜索二叉树:
采用中序遍历,如果是搜索二叉树,中序遍历的结果是递增的
采用递归(左树是搜索二叉树、右树是搜索二叉树,且左树的根节点小于当前值,右树的根节点大于当前值)
对应leetcode:https://leetcode.cn/problems/validate-binary-search-tree/
采用递归:
public boolean isValidBST(TreeNode root) {
return isBinarySearchTree(root).isBST;
}
private Info isBinarySearchTree(TreeNode node) {
if (node == null) {
return null;
}
Info leftInfo = isBinarySearchTree(node.left);
Info rightInfo = isBinarySearchTree(node.right);
int max = node.val;
int min = node.val;
boolean isBST = true;
if (leftInfo != null) {
max = Math.max(max, leftInfo.max);
min = Math.min(min, leftInfo.min);
isBST = leftInfo.isBST && (leftInfo.max < node.val);
}
if (rightInfo != null) {
max = Math.max(max, rightInfo.max);
min = Math.min(min, rightInfo.min);
isBST = isBST && rightInfo.isBST && (rightInfo.min > node.val);
}
return new Info(max, min, isBST);
}
static class Info {
public int max;
public int min;
public boolean isBST;
public Info(int max, int min, boolean isBST) {
this.max = max;
this.min = min;
this.isBST = isBST;
}
}
二叉树路径总和
对应Leetcode:https://leetcode.cn/problems/path-sum/
解法:
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
return process(root, targetSum, 0);
}
public boolean process(TreeNode node, int targetSum, int sum) {
// 叶子节点
if (node.left == null && node.right == null) {
return targetSum == sum + node.val;
}
boolean result = false;
if (node.left != null) {
result |= process(node.left, targetSum, sum + node.val);
}
if (node.right != null) {
result |= process(node.right, targetSum, sum + node.val);
}
return result;
}
}
二叉树收集达标路径总和
Leetcode: https://leetcode.cn/problems/path-sum-ii/
解法(自己独立写的性能很差):
class Solution {
private static List<List<Integer>> pathList = null;
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
pathList = new ArrayList<>();
if (root == null) {
return new ArrayList<>();
}
process(root, targetSum, 0, new ArrayList<>());
return pathList;
}
public void process(TreeNode node, int targetSum, int sum, List<Integer> path) {
// 无论是叶子节点还是非叶子节点,都要加入到path中
path.add(node.val);
// 如果是叶子节点,判断是否符合路径和,如果符合就加入路径到路径列表
if (node.left == null && node.right == null) {
if (targetSum == sum + node.val) {
pathList.add(path);
}
return;
}
// 如果不是叶子节点
if (node.left != null) {
process(node.left, targetSum, sum + node.val, new ArrayList<>(path));
}
if (node.right != null) {
process(node.right, targetSum, sum + node.val, new ArrayList<>(path));
}
}
}
堆
优先级队列
定义:优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。
优先级队列的逻辑存储结构并不是队列,他是一种具有FIFO特征的堆结构(也就是树形结构)。每次从优先级队列中取出的是具有最高优先权的元素,内部按照优先权堆数据元素排序。
比如在Java中的PriorityQueue
类,就是优先级队列的实现,默认是一个小根堆(先弹出最小的元素):
public static void main(String[] args) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
heap.add(6);
heap.add(2);
heap.add(3);
heap.add(1);
heap.add(7);
while (!heap.isEmpty()) {
System.out.print(heap.poll() + " "); // 1 2 3 6 7
}
}