删除元素

反转一个列表

队列底层也可以使用动态数组实现，并且各项接口也可以优化到O(1)的时间复杂度，这个用数组实现并且优化之后的队列叫，循环队列

向下取整：只取前面的整数

向上取整：如果小数不为0，前面的整数加1，小数为0，只取整数

数组随机访问

随机访问速度快

elements[n]的效率与n是多少无关

动态数组链表复杂度分析

add

问：什么情况下适合使用均摊复杂度

经过连续多次复杂度比较低的情况后，出现个别复杂度比较高

动态数组缩容

如果内存比较紧张，动态数组比较多的剩余空间可以考虑进行缩容操作

如果扩容倍数，缩容时机设计不当，有可能导致复杂度振荡

双向链表

使用双向链表可以提升链表综合性能

双向链表node法

双向链表add

remove

单向循环列表

单向add

单向remove

双向循环列表

如何发挥循环列表最大威力

可以考虑1个成员变量，3个方法

current ：用于指向某个节点

void reset() 让current 指向头节点 first

E next 让 current 往后走一步，也就是 current = current.next

E remove() ：删除 current 指向的节点，删除成功后让 current 指向下一个节点

静态列表

栈

栈是一种特殊的线性表，只能在一端进行操作

往栈中添加元素操作，push 入栈

从栈中移除元素操作

pop 出栈，移除栈顶元素

后进先出

栈接口

int size() 元素数量

boolean isEmpty()是否是空

void push(E element)入栈

E top();获取栈顶元素

void clear() 清空

栈 括号面试题

判断括号的有效性可以使用「栈」这一数据结构来解决。我们遍历给定的字符串 s。当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶。当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 s 无效，返回 False。为了快速判断括号的类型，我们可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。在遍历结束后，如果栈中没有左括号，说明我们将字符串 s 中的所有左括号闭合，返回 True，否则返回 False。注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 /text{False}False，省去后续的遍历判断过程。class Solution { public boolean isValid(String s) { int n = s.length(); if (n % 2 == 1) { return false; } Map pairs = new HashMap() {{ put(')', '('); put(']', '['); put('}', '{'); }}; Deque stack = new LinkedList(); for (int i = 0; i 有效的括号

遇见左字符，将左字符入栈

如果栈是空的，说明括号无效

如果栈不是空的将栈顶字符出栈，和右字符匹配

如果左右字符不配，说明括号无效

如果左右字符匹配，继续扫描下一个字符

所有字符扫描完毕后

栈是空，说明括号有效

栈不是空，说明括号无效

队列

队列是特殊线性表，只能在头尾两端进行操作

队尾(rear) :只能从队尾添加元素，一般叫 enQueue 入队

对头(front) 只能从队头移除元素，一般叫 deQueue 出队

先进先出原则

队列接口设计

int size() 元素数量

boolean isEmpty()

void clear()

void enQueue (E element)

E deQueue() 出队

E front() 获取队列头元素

动态数组、链表

优先使用双向链表，因为队列主要是往头尾操作元素

用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：实现 MyQueue 类：void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空，返回 true ；否则，返回 false说明：你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。 private int front;public void push(int x) { if (s1.empty()) frOnt= x; while (!s1.isEmpty()) s2.push(s1.pop()); s2.push(x); while (!s2.isEmpty()) s1.push(s2.pop());}复杂度分析时间复杂度：O(n)O(n)对于除了新元素之外的所有元素，它们都会被压入两次，弹出两次。新元素只被压入一次，弹出一次。这个过程产生了 4n + 24n+2 次操作，其中 nn 是队列的大小。由于 压入 操作和 弹出 操作的时间复杂度为 O(1)O(1)， 所以时间复杂度为 O(n)O(n)。空间复杂度：O(n)O(n)需要额外的内存来存储队列中的元素。

双端队列

双端队列是在头尾两端添加，删除队列

int size()boolean isEmpty()◼ void clear(); // 清空◼ void enQueueRear(E element); // 从队尾入队◼ E deQueueFront(); // 从队头出队◼ void enQueueFront(E element); // 从队头入队◼ E deQueueRear(); // 从队尾出队◼ E front(); // 获取队列的头元素◼ E rear(); // 获取队列的尾元素

循环队列底层使用动态数组实现，并且各项接口也可以优化到O(1)

时间复杂度

◼ 这个用数组实现并且优化之后的队列也叫做：循环队列

循环队列

循环双端队列

%运算符优化

尽量避免使用乘*、除/、模%、浮点数运算，效率低下

二叉树

节点根节点，父节点，子节点，兄弟节点

节点的度：子树的个数

树的度:所有节点度中最大值

叶子节点：度是0节点

非叶子节点：度不为0的节点

层数：根节点在1层，根节点子节点在2层

节点深度：从根节点到当前节点唯一路径上节点总数

节点的高度：从当前节点到最远叶子节点路径上节点总数

树的深度：所有节点深度最大值

树的高度：所有节点高度最大值

^{树的深度等于树的高度}

有序树，无序树，森林

有序树树中任意节点的子节点之间有顺序关系无序树树中任意节点的子节点之间没有顺序关系也称为“自由树森林由 m（m ≥ 0）棵互不相交的树组成的集合

二叉树特点

每个节点度最大是2

左子树和右子树有顺序

即使是某节点只有一个子树，也要区分左右子树

非空二叉树的第 i 层，最多有 2^i-1 个节点（ i ≥ 1 ）

在高度为 h 的二叉树上最多有 2^h-1个结点（ h ≥ 1 ）

对于任何一棵非空二叉树，如果叶子节点个数为 n0，度为 2 的节点个数为 n2，则有: n0 = n2 + 1 假设度为 1 的节点个数为 n1，那么二叉树的节点总数 n = n0 + n1 + n2

二叉树的边数 T = n1 + 2 * n2 = n – 1 = n0 + n1 + n2 – 1

因此 n0 = n2 + 1

真二叉树

所有节点度都要么是0，要么是2

满二叉树

满二叉树：所有节点的度都要么为 0，要么为 2。且所有的叶子节点都在最后一层

假设满二叉树的高度为 h（ h ≥ 1 ），那么 第 i 层的节点数量 2^i-1

叶子节点数量2^h-1

✓n = 2 h − 1 = 2 0 + 2 1 + 2 2 + ⋯ + 2 h−1

h = log2(n + 1)

完全二叉树

叶子节点只会出现最后2层，最后1层叶子节点都靠左对齐

完全二叉树从根节点到倒数第二层是一个满二叉树

满二叉树一定时完全二叉树，完全二叉树不一定是满二叉树

性质

度为1的节点只有左子树

度是1的节点要么是1个要么是0个

同样是节点数量的二叉树，完全二叉树高度最小

一棵有 n 个节点的完全二叉树（n > 0），从上到下、从左到右对节点从 1 开始进行编号，对任意第 i 个节点如果 i = 1 ，它是根节点如果 i > 1 ，它的父节点编号为 floor( i / 2 )如果 2i ≤ n ，它的左子节点编号为 2i如果 2i > n ，它无左子节点如果 2i + 1 ≤ n ，它的右子节点编号为 2i + 1如果 2i + 1 > n ，它无右子节点一棵有 n 个节点的完全二叉树（n > 0），从上到下、从左到右对节点从 0 开始进行编号，对任意第 i 个节点如果 i = 0 ，它是根节点如果 i > 0 ，它的父节点编号为 floor( (i – 1) / 2 )如果 2i + 1 ≤ n – 1 ，它的左子节点编号为 2i + 1如果 2i + 1 > n – 1 ，它无左子节点如果 2i + 2 ≤ n – 1 ，它的右子节点编号为 2i + 2如果 2i + 2 > n – 1 ，它无右子节点◼ 如果一棵完全二叉树有 768 个节点，求叶子节点的个数假设叶子节点个数为 n0，度为 1 的节点个数为 n1，度为 2 的节点个数为 n2总结点个数 n = n0 + n1 + n2，而且 n0 = n2 + 1✓ n = 2n0 + n1 – 1完全二叉树的 n1 要么为 0，要么为 1✓ n1为1时，n = 2n0，n 必然是偶数➢ 叶子节点个数 n0 = n / 2，非叶子节点个数 n1 + n2 = n / 2✓ n1为0时，n = 2n0 – 1，n 必然是奇数➢ 叶子节点个数 n0 = (n + 1) / 2，非叶子节点个数 n1 + n2 = (n – 1) / 2叶子节点个数 n0 = floor( (n + 1) / 2 ) = ceiling( n / 2 ) 非叶子节点个数 n1 + n2 = floor( n / 2 ) = ceiling( (n – 1) / 2 ) 因此叶子节点个数为 384

二叉树遍历

把所有元素都访问一遍

线性数据结构遍历比较简单

正序遍历

逆序遍历

前序

中序

后序

层序

前序遍历

先访问根节点，前序遍历左子树，前序遍历右子树

中序遍历

左子树 ，根节点，右子树

后序遍历

左子树，右子树，根节点

层序遍历

从上到下，从左到右依次遍历

◼ 实现思路：使用队列1. 将根节点入队2. 循环执行以下操作，直到队列为空将队头节点 A 出队，进行访问将 A 的左子节点入队将 A 的右子节点入队/** * 前序遍历 */public void preorderTraversal() {preorderTraversal(root);}private void preorderTraversal(Node node) {if (node == null) return;System.out.println(node.element);preorderTraversal(node.left);preorderTraversal(node.right);}/** * 中序遍历 */public void inorderTraversal() {inorderTraversal(root);}private void inorderTraversal(Node node) {if (node == null) return;inorderTraversal(node.left);System.out.println(node.element);inorderTraversal(node.right);}/** * 后序遍历 */public void postorderTraversal() {postorderTraversal(root);}private void postorderTraversal(Node node) {if (node == null) return;postorderTraversal(node.left);postorderTraversal(node.right);System.out.println(node.element);}/** * 层序遍历 */public void levelOrderTraversal() {if (root == null) return;Queue queue = new LinkedList();queue.offer(root);while (!queue.isEmpty()) {Node node = queue.poll();System.out.println(node.element);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}} public static abstract class Visitor { boolean stop; /** * @return 如果返回true，就代表停止遍历 */ public abstract boolean visit(E element); }public void preorder(Visitor visitor) { if (visitor == null) return; preorder(root, visitor); } private void preorder(Node node, Visitor visitor) { if (node == null || visitor.stop) return; visitor.stop = visitor.visit(node.element); preorder(node.left, visitor); preorder(node.right, visitor); } public void inorder(Visitor visitor) { if (visitor == null) return; inorder(root, visitor); } private void inorder(Node node, Visitor visitor) { if (node == null || visitor.stop) return; inorder(node.left, visitor); if (visitor.stop) return; visitor.stop = visitor.visit(node.element); inorder(node.right, visitor); } public void postorder(Visitor visitor) { if (visitor == null) return; postorder(root, visitor); } private void postorder(Node node, Visitor visitor) { if (node == null || visitor.stop) return; postorder(node.left, visitor); postorder(node.right, visitor); if (visitor.stop) return; visitor.stop = visitor.visit(node.element); }

优化

public void levelOrder(Visitor visitor) { if (root == null || visitor == null) return; Queue queue = new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { Node node = queue.poll(); if (visitor.visit(node.element)) return; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } }

树状打印二叉树

@Override public String toString() { StringBuilder sb = new StringBuilder(); toString(root, sb, ""); return sb.toString(); } private void toString(Node node, StringBuilder sb, String prefix) { if (node == null) return; toString(node.left, sb, prefix + "L---"); sb.append(prefix).append(node.element).append("/n"); toString(node.right, sb, prefix + "R---"); }

完全二叉树判断

public boolean isComplete() { if (root == null) return false; Queue queue = new LinkedList(); queue.offer(root); boolean leaf = false; while (!queue.isEmpty()) { Node node = queue.poll(); if (leaf if (node.left != null) { queue.offer(node.left); } else if (node.right != null) { // node.left == null } if (node.right != null) { queue.offer(node.right); } else { // node.right == null leaf = true; } } return true; }

计算二叉树的高度

public int height() { if (root == null) return 0; // 树的高度 int height = 0; // 存储着每一层的元素数量 int levelSize = 1; Queue queue = new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { Node node = queue.poll(); levelSize--; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } if (levelSize == 0) { // 意味着即将要访问下一层 levelSize = queue.size(); height++; } } return height; } public int height2() { return height(root); } private int height(Node node) { if (node == null) return 0; return 1 + Math.max(height(node.left), height(node.right)); }

反转二叉树

package datastruct.tree.翻转二叉树;import java.util.LinkedList;import java.util.Queue;public class invertTree { // 首先我们考虑的不是用什么方式遍历的问题，而是考虑题目想要干什么 public TreeNode invertTree1(TreeNode root){ if (root == null) return root; TreeNode tmp = root.left; root.left = root.right; root.right = tmp; invertTree1(root.left); invertTree1(root.right); return root; }// public TreeNode invertTree(TreeNode root) {// if (root == null) return root;//// TreeNode tmp = root.left;// root.left = root.right;// root.right = tmp;//// invertTree(root.left);// invertTree(root.right);//// return root;// }//public TreeNode invertTree(TreeNode root) {// if (root == null) return root;//// invertTree(root.left);// invertTree(root.right);//// TreeNode tmp = root.left;// root.left = root.right;// root.right = tmp;//// return root;// }//public TreeNode invertTree(TreeNode root) {// if (root == null) return root;//// invertTree(root.left);//// TreeNode tmp = root.left;// root.left = root.right;// root.right = tmp;//// invertTree(root.left);//// return root;// } // 层序遍历 public TreeNode invertTree(TreeNode root) { if (root == null) return root; Queue queue = new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); TreeNode tmp = node.left; node.left = node.right; node.right = tmp; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } return root; }}

遍历应用

前序遍历

树状结构展示

中序遍历

二叉搜索树中序遍历按升序或者降序处理节点

后序遍历

先子后父

层序遍历

计算二叉树的高度

根据遍历结果重构二叉树

前序遍历 + 中序遍历

后序遍历 + 中序遍历

前序遍历 + 后序遍历

前+中

◼ 前序遍历：4 2 1 3 6 5 ◼ 中序遍历：1 2 3 4 5 6

前驱节点和后继节点

private Node predecessor(Node node) { if (node == null) return null; // 前驱节点在左子树当中（left.right.right.right....） Node p = node.left; if (p != null) { while (p.right != null) { p = p.right; } return p; } // 从父节点、祖父节点中寻找前驱节点 while (node.parent != null } // node.parent == null // node == node.parent.right return node.parent; } private Node successor(Node node) { if (node == null) return null; // 前驱节点在左子树当中（right.left.left.left....） Node p = node.right; if (p != null) { while (p.left != null) { p = p.left; } return p; } // 从父节点、祖父节点中寻找前驱节点 while (node.parent != null } return node.parent; }

二叉搜索树

在 n 个动态的整数中搜索某个整数？（查看其是否存在）◼ 针对这个需求，有没有更好的方案？使用二叉搜索树，添加、删除、搜索的最坏时间复杂度均可优化至：O(logn)0 1 2 3 4 5 6 7 8 931 66 17 15 28 20 59 88 45 56◼ 如果维护一个有序的动态数组，使用二分搜索，最坏时间复杂度：O(logn)但是添加、删除的平均时间复杂度是 O(n)0 1 2 3 4 5 6 7 8 915 17 20 28 31 45 56 59 66 88◼ 假设使用动态数组存放元素，从第 0 个位置开始遍历搜索，平均时间复杂度：O(n)

删除节点

删除度为0的节点，删除叶子节点

node == node.parent.left✓ node.parent.left = nullnode == node.parent.right✓ node.parent.right = nullnode.parent == null✓ root = null

删除度为1的节点

用子节点替代源节点的位置

child 是 node.left 或者 child 是 node.right

用 child 替代 node 的位置✓ 如果 node 是左子节点➢ child.parent = node.parent➢ node.parent.left = child✓ 如果 node 是右子节点➢ child.parent = node.parent➢ node.parent.right = child✓ 如果 node 是根节点➢ root = child➢ child.parent = null

删除度为2的节点(删除根节点)

◼ 举例：先删除 5、再删除 4◼ 先用前驱或者后继节点的值覆盖原节点的值◼ 然后删除相应的前驱或者后继节点◼ 如果一个节点的度为 2，那么它的前驱、后继节点的度只可能是 1 和 0

private void remove(Node node) { if (node == null) return; size--; if (node.hasTwoChildren()) { // 度为2的节点 // 找到后继节点 Node s = successor(node); // 用后继节点的值覆盖度为2的节点的值 node.element = s.element; // 删除后继节点 node = s; } // 删除node节点（node的度必然是1或者0） Node replacement = node.left != null ? node.left : node.right; if (replacement != null) { // node是度为1的节点 // 更改parent replacement.parent = node.parent; // 更改parent的left、right的指向 if (node.parent == null) { // node是度为1的节点并且是根节点 root = replacement; } else if (node == node.parent.left) { node.parent.left = replacement; } else { // node == node.parent.right node.parent.right = replacement; } } else if (node.parent == null) { // node是叶子节点并且是根节点 root = null; } else { // node是叶子节点，但不是根节点 if (node == node.parent.left) { node.parent.left = null; } else { // node == node.parent.right node.parent.right = null; } } }------------------------------找后继节点代码 private Node successor(Node node) { if (node == null) return null; // 前驱节点在左子树当中（right.left.left.left....） Node p = node.right; if (p != null) { while (p.left != null) { p = p.left; } return p; } // 从父节点、祖父节点中寻找前驱节点 while (node.parent != null } return node.parent; }--------------node private Node node(E element) { Node node = root; while (node != null) { int cmp = compare(element, node.element); if (cmp == 0) return node; if (cmp > 0) { node = node.right; } else { // cmp <0 node = node.left; } } return null; }