湛江做网站说,去哪找想做网站的客户,wordpress升级快速,四川企业宣传片制作公司二叉树的Morris(莫里斯)遍历
本文参考链接#xff1a;https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/490846864/ 文章目录 二叉树的Morris(莫里斯)遍历模板代码前序遍历中序遍历后序遍历 Morris 遍历使用二叉树节点中大量指向 null 的指针…二叉树的Morris(莫里斯)遍历
本文参考链接https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/490846864/ 文章目录 二叉树的Morris(莫里斯)遍历模板代码前序遍历中序遍历后序遍历 Morris 遍历使用二叉树节点中大量指向 null 的指针时间复杂度O(n)额外空间复杂度O(1)。
Morris 的整体思路就是将 以某个根结点开始找到它左子树的最右侧节点之后与这个根结点进行连接。 我们可以从图中看到连接之后指针是可以完整的从根节点顺着下一个节点遍历将整棵树遍历完毕直到 7 这个节点右侧没有指向。
模板代码
首先介绍morris的模板代码带*的注释表示该行为指定遍历所要增加的内容可以先不管。
模板代码的流程图如下所示 public ListInteger traversal(TreeNode root) {ListInteger res new ArrayList();if (root null) {return res;}//1.定义cur和prevTreeNode cur root;TreeNode prev null;//2.当cur不为空时while (cur ! null) {//2.1prev为cur左子树prev cur.left;//2.2prev不为空时if (prev ! null) {//2.2.1用prev找到左子树最右侧节点while (prev.right ! null prev.right ! cur) {prev prev.right;}//2.2.2prev右子树不为空时连接if (prev.right null) {prev.right cur;//*前res.add(cur.val);cur cur.left;} else { //2.2.3prev右子树不为空时断开连接prev.right null;//*中res.add(cur.val); *后print(cur.left)cur cur.right;}} else { //2.3prev为空时//*前中res.add(cur.val);cur cur.right;}}//*后print(root)return res;
}前序遍历
public ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayList();if (root null) {return res;}//1.定义cur和prevTreeNode cur root;TreeNode prev null;//2.当cur不为空时while (cur ! null) {//2.1prev为cur左子树prev cur.left;//2.2prev不为空时if (prev ! null) {//2.2.1用prev找到左子树最右侧节点while (prev.right ! null prev.right ! cur) {prev prev.right;}//2.2.2prev右子树不为空时连接if (prev.right null) {prev.right cur;res.add(cur.val);cur cur.left;} else { //2.2.3prev右子树不为空时断开连接prev.right null;cur cur.right;}} else { //2.3prev为空时res.add(cur.val);cur cur.right;}}return res;
}
中序遍历
public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayList();if (root null) {return res;}//1.定义cur和prevTreeNode cur root;TreeNode prev null;//2.当cur不为空时while (cur ! null) {//2.1prev为cur左子树prev cur.left;//2.2prev不为空时if (prev ! null) {//2.2.1用prev找到左子树最右侧节点while (prev.right ! null prev.right ! cur) {prev prev.right;}//2.2.2prev右子树不为空时连接if (prev.right null) {prev.right cur;cur cur.left;} else { //2.2.3prev右子树不为空时断开连接prev.right null;res.add(cur.val);cur cur.right;}} else { //2.3prev为空时res.add(cur.val);cur cur.right;}}return res;
}后序遍历
当连接已完成时断开连接后打印下层的单链表比如返回到2时打印4返回到1时打印52涉及到了逆序打印单链表的内容。注意应该是打印下一层而不是当前层。循环结束后打印根节点所在的一侧即731。 ListInteger res new ArrayList();
public ListInteger postorderTraversal(TreeNode root) {if (root null) {return res;}//1.定义cur和prevTreeNode cur root;TreeNode prev null;//2.当cur不为空时while (cur ! null) {//2.1prev为cur左子树prev cur.left;//2.2prev不为空时if (prev ! null) {//2.2.1用prev找到左子树最右侧节点while (prev.right ! null prev.right ! cur) {prev prev.right;}//2.2.2prev右子树不为空时连接if (prev.right null) {prev.right cur;cur cur.left;} else { //2.2.3prev右子树不为空时断开连接prev.right null;print(cur.left); //打印左子树cur cur.right;}} else { //2.3prev为空时cur cur.right;}}print(root); //打印根节点所在一侧return res;
}//打印链表
public void print(TreeNode head) {TreeNode revList reverseList(head);TreeNode cur revList;while (cur ! null) {res.add(cur.val);cur cur.right;}reverseList(revList);
}//翻转单链表
public TreeNode reverseList(TreeNode head) {TreeNode cur head;TreeNode prev null;while (cur ! null) {TreeNode next cur.right;cur.right prev;prev cur;cur next;}return prev;
}
