各种数据结构的遍历框架

《labuladong 的算法⼩抄》学习笔记

数组遍历框架，典型的线性迭代结构：

void traverse(int[] arr) {
for (int i = 0; i < arr.length; i++) {
// 迭代访问 arr[i]
}
}

 

链表遍历框架，兼具迭代和递归结构：

/* 基本的单链表节点 */
class ListNode {
int val;
ListNode next;
}
void traverse(ListNode head) {
for (ListNode p = head; p != null; p = p.next) {
// 迭代访问 p.val
}
}
void traverse(ListNode head) {
// 递归访问 head.val
traverse(head.next)
}

 

⼆叉树遍历框架，典型的⾮线性递归遍历结构：

/* 基本的⼆叉树节点 */
class TreeNode {
int val;
TreeNode left, right;
}
void traverse(TreeNode root) {
traverse(root.left)
traverse(root.right)
}

 

⼆叉树框架可以扩展为 N 叉树的遍历框架：

/* 基本的 N 叉树节点 */
class TreeNode {
int val;
TreeNode[] children;
}
void traverse(TreeNode root) {
for (TreeNode child : root.children)
traverse(child)
}

 foreach语句无非就是for循环的封装，为了提高开发速度才创造出来的。他其实跟for循环一样，只不过写起来比较简便，他是1.5版本才出来的一种封装语法。并没有什么奇特之处他里面的机制就是for循环。如图所示：