| 整理：Java二叉树遍历（递归、迭代、Morris）原创图解+代码 | 您所在的位置：网站首页 › 华为nova2后置摄像头像素怎么调 › 整理：Java二叉树遍历（递归、迭代、Morris）原创图解+代码 |
整理：Java二叉树遍历（递归、迭代、Morris）原创图解+代码
|
本文不讨论二叉树层次遍历 刷题的时候看到一些二叉树遍历的解法，整理在这里作为笔记，也分享给大家 语言是 Java 的，我会采取代码+图解+说明形式来尽可能讲明白每种遍历方式 目录 一些准备 树节点类代码（TreeNode） 树节点类图解 工程文件结构 工程文件说明 递归解法（RecursiveTraversal） 递归解法复杂度 前序（递归） 中序（递归） 后序（递归） 迭代解法（IterativeTraversal） 迭代解法复杂度 前序（迭代，单层循环） 前序（迭代，双层循环） 中序（迭代，双层循环） 后序（迭代，单层循环） 后序（迭代，双层循环） 5种迭代解法图解 Morris 解法（MorrisTraversal） Morris 解法复杂度 前序（Morris） 中序（Morris） 一些准备为了便于整理和展示，我建立了一个简单的纯 Java 工程来测试各种解法 树节点类代码（TreeNode）一个简单的树节点类： public 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; } } 树节点类图解这是一棵二叉树，它拥有四个树节点，左侧虚线框内是它的简化图
根左右 public static void preOrder(TreeNode root) { if (root == null) return; System.out.print(root.val + " "); preOrder(root.left); preOrder(root.right); } 中序（递归）左根右 public static void inOrder(TreeNode root) { if (root == null) return; inOrder(root.left); System.out.print(root.val + " "); inOrder(root.right); } 后序（递归）左右根 public static void postOrder(TreeNode root) { if (root == null) return; postOrder(root.left); postOrder(root.right); System.out.print(root.val + " "); } 迭代解法（IterativeTraversal） 使用辅助数据结构（自定义栈）代替系统栈，有效降低栈空间消耗和溢出风险避免了大量函数调用所产生的开销代码复杂度相对较高 然而，这并不意味着迭代解法更难以理解 迭代解法复杂度 时间复杂度空间复杂度O(n)O(n) 前序（迭代，单层循环）需要区分的一点是： 递归中，进入的是子树迭代中，压入的是节点尽管子树和节点看起来都是一个 TreeNode，但它们之间存在一些区别！ 另外，这里使用 LinkedList（双向链表），而非 Stack 因为 Stack 底层是基于数组实现的，对于频繁插入和删除的场景下，并不太适合 注意：选择数组或链表实现栈的优劣取决于二叉树的分布特点 对于单层循环方式，我们利用栈的后进先出特点，要先压入右子节点，再压入左子节点 public static void preOrder1(TreeNode root) { // 前序单层循环 if (root == null) return; Deque stack = new LinkedList(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); System.out.print(node.val + " "); if (node.right != null) stack.push(node.right); if (node.left != null) stack.push(node.left); } } 前序（迭代，双层循环）内循环中压入子树的所有左子节点 public static void preOrder2(TreeNode root) { // 前序双层循环 if (root == null) return; TreeNode node = root; Deque stack = new LinkedList(); while (!stack.isEmpty() || node != null) { while (node != null) { System.out.print(node.val + " "); stack.push(node); node = node.left; } node = stack.pop(); node = node.right; } } 中序（迭代，双层循环）对于单层循环方式，我们必须先把根节点压入栈中，所以它无法实现中序遍历 内循环中压入子树的所有左子节点 public static void inOrder(TreeNode root) { // 中序双层循环 if (root == null) return; TreeNode node = root; Deque stack = new LinkedList(); while (!stack.isEmpty() || node != null) { while (node != null) { stack.push(node); node = node.left; } node = stack.pop(); System.out.print(node.val + " "); node = node.right; } } 后序（迭代，单层循环）对于单层循环方式，后序遍历可以采用一个讨巧的办法：逆序输出 这需要额外的开销（对于下面的代码，既有辅助栈的空间开销，也有逆序的时间开销） public static void postOrder1(TreeNode root) { // 后序单层循环 if (root == null) return; Deque stack1 = new LinkedList(); Deque stack2 = new LinkedList(); stack1.push(root); while (!stack1.isEmpty()) { TreeNode node = stack1.pop(); stack2.push(node); if (node.left != null) stack1.push(node.left); if (node.right != null) stack1.push(node.right); } while (!stack2.isEmpty()) { System.out.print(stack2.pop().val + " "); } } 后序（迭代，双层循环）内循环中压入子树的所有左子节点 public static void postOrder2(TreeNode root) { // 后序双层循环 if (root == null) return; TreeNode node = root; TreeNode prev = null; Deque stack = new LinkedList(); while (!stack.isEmpty() || node != null) { while (node != null) { stack.push(node); node = node.left; } node = stack.pop(); if (node.right == null || node.right == prev) { System.out.print(node.val + " "); prev = node; node = null; } else { stack.push(node); node = node.right; } } } 5种迭代解法图解我绘制了5种解法的核心代码 N-S 图，以便于横向对比
|
【本文地址】
公司简介
联系我们