神奇的 Morris 树遍历

神奇的 Morris 树遍历

D瓜哥
无论是在计算机课上,还是在网上,对数据结构有一定了解的童鞋,应该都对树的遍历不陌生。常见的遍历方式有如下两种: 基于栈的遍历:需要额外的空间复杂度。实现略复杂。 基于递归的遍历:实现简单。空间复杂度上,与栈类似,只是这里的栈维护是由系统自动完成的。 在看左程云的《程序员代码面试指南》时,里面介绍了一种只需 O(1) 的额外空间复杂度的遍历方法:Morris 树遍历。感觉非常神奇。这里给大家介绍一下。 Morris 树遍历的神奇之处在于,它充分利用了树里面大量的空闲节点(比如叶子节点的左右子树节点就为空,可以利用起来)来建立起必要的连接,推动遍历的进行。核心思想非常简单:找出当前节点左子树的最右节点,此时最右节点的右子树为空,将最右节点的右子树指向当前节点。然后左移,递归完成所有相关连接。没有左子树时,则向右移动,依次完成上述操作。我们来结合图来说明。如图: 图 1. Morris 树遍历 如上图所示,当访问根节点 4 时,它的左子树的最右节点就是 3,将 3 的右子树指向当前节点 4,如线条 ⑥ 所示。向左启动,建立起 1 到 2 的连接 ④。再向左移动到 1,1 没有左子树,则向右移动,此时就利用上了刚刚建立起的连接 ④。依次类推,即可完成遍历。在遍历过程中,也需要把建立的临时连接给取消掉。 /** * Morris 树遍历 * * @author D瓜哥 · https://www.diguage.com */ public void morris(TreeNode head) { TreeNode curr = head; TreeNode mostRight = null; while (curr != null) { // 当前节点左子树的最右节点,当然是从左子树开始了 mostRight = curr.left; if (mostRight != null) { // 左子树不为空,则找出左子树的最右节点 while (mostRight.right != null // 由于需要建立最右节点到当前节点的连接,所以,需要判断是否已建立连接来打破死循环 && mostRight.right != curr) { mostRight = mostRight.right; } if (mostRight.right == null) { // 最右节点的右子树为空,则第一次访问,那么建立起连接 mostRight.right = curr; curr = curr.left; continue; } else { // 最右节点的右子树不为空,则第二次访问,打破连接,恢复原貌 mostRight.right = null; } } // 最子树为空,则向右移动 curr = curr.right; } } 根据代码,结合图示,很容易得到 Morris 遍历的结果: 4、2、1、22、3、42、6、5、62、7。分析这个结果可以发现:有左子树的节点都会被访问两次。 前根遍历 那么该树的前根遍历是什么呢?这个也很容易得出:4、2、1、3、6、5、7。如何从 Morris 遍历中,得到前根遍历的结果呢?对比两边的结果,可以很容易发现:将访问两次的元素,只在第一次访问时输出;只访问一次的原始直接输出即可。代码如下: /** * Morris 树前根遍历 * * @author D瓜哥 · https://www.diguage.com */ public void morrisPre(TreeNode head) { TreeNode curr = head; TreeNode mostRight = null; while (curr != null) { // 当前节点左子树的最右节点,当然是从左子树开始了 mostRight = curr.left; if (mostRight != null) { // 左子树不为空,则找出左子树的最右节点 while (mostRight.right != null // 由于需要建立最右节点到当前节点的连接,所以,需要判断是否已建立连接来打破死循环 && mostRight.right != curr) { mostRight = mostRight.right; } if (mostRight.right == null) { // 最右节点的右子树为空,则第一次访问,那么建立起连接 mostRight.right = curr; // 第一次访问时,即输出 System.out.print(curr.val + " "); curr = curr.left; continue; } else { // 最右节点的右子树不为空,则第二次访问,打破连接,恢复原貌 mostRight.right = null; } } else { // 前面内容已经分析过:有左子树的节点就会被访问两次 // 那么没有左子树的节点,就自会访问一次,访问到时直接输出即可。 System.out.print(curr.val + " "); } // 最子树为空,则向右移动 curr = curr.right; } }
题解:538.把二叉搜索树转换为累加树

题解:538.把二叉搜索树转换为累加树

D瓜哥
题目描述 题目是 LeetCode 的第 538 题: 把二叉搜索树转换为累加树。 给出二叉搜索树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 提醒一下,二叉搜索树满足下列约束条件: 节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。 思路分析 一棵二叉搜索树,如果是中根遍历,那么,其序列正好是一个升序序列。但,题目要求的是大于等于自身的节点值之和。正常的中根遍历是“左中右”,反过来“右中左”,就是降序序列,累计求和就符合题目要求了。 解题代码 中序遍历,可以用栈,也可以使用 Morris 遍历。在 题解:找到二叉搜索树中两个错误的节点 中就是用了 Morris 遍历。网上也很少有反向的 Morris 中根遍历。正好练习一下。 /** * 基于 Morris 的倒序中根遍历 * * @author D瓜哥 · https://www.diguage.com */ public TreeNode convertBST(TreeNode root) { int sum = 0; // 反向 Morris TreeNode cur = root; TreeNode mostLeft = null; while (cur != null) { // 向右转 mostLeft = cur.right; if (mostLeft != null) { // 寻找最左边的节点 while (mostLeft.left != null && mostLeft.left != cur) { mostLeft = mostLeft.left; } if (mostLeft.left == null) { // 第一次访问,将最左节点的左子树指向当前节点 mostLeft.left = cur; cur = cur.right; continue; } else { // 第二次访问,掐断中间建立的连接 mostLeft.left = null; } } // 计算累加和 sum += cur.val; cur.val = sum; cur = cur.left; } return root; } 得益于 Morris 的优秀本质,这个解法的时间复杂度是: O(n),空间复杂度是: O(1)。 关于 Morris 树遍历的更多介绍,请看: 神奇的 Morris 树遍历。
题解:找到二叉搜索树中两个错误的节点

题解:找到二叉搜索树中两个错误的节点

D瓜哥
题目描述 一棵二叉树原本是二叉搜索树,但是其中有两个节点调换了位置,使得这棵二叉树不再是二叉搜索树,请按升序输出这两个错误节点的值。(每个节点的值各不相同) 思路分析 一棵二叉搜索树,如果是中序遍历,那么,其序列正好是一个升序序列。如果序列中间出现了降序,那么就是树中错误的节点。这里有两种情况需要考虑: 如果两个节点正好相邻,那么降序的两个节点就是题目要求的节点。 如果两个节点不相邻,就会出现两次降序。很容易想到,“大”的元素跑前面,“小”的元素跑后面。在进行比较的时候,第一个降序时,前面大的元素是错误节点;第二次降序时,则是后面小的元素是错误节点。 有了上面的分析,就可以写代码了。 解题代码 中序遍历,可以用栈,也可以使用 Morris 遍历。前面正好学习了一下 Morris(详情请看: 神奇的 Morris 树遍历),借此机会练练手: /** * 基于 Morris 的中根遍历 * * @author D瓜哥 · https://www.diguage.com */ public TreeNode[] getErrs(TreeNode head) { TreeNode[] result = new TreeNode[2]; TreeNode curr = head; TreeNode mostRight = null; TreeNode prior = null; while (curr != null) { mostRight = curr.left; if (mostRight != null) { while (mostRight.right != null && mostRight.right != curr) { mostRight = mostRight.right; } if (mostRight.right == null) { mostRight.right = curr; curr = curr.left; continue; } else { mostRight.right = null; } } if (prior != null) { if (prior.val > curr.val) { if (result[0] == null) { result[0] = curr; result[1] = prior; } else { result[0] = curr; } } } prior = curr; curr = curr.right; } return result; } 得益于 Morris 的优秀本质,这个解法的时间复杂度是: O(n),空间复杂度是: O(1)。