左神算法笔记——Morris遍历
2020-04-11 本文已影响0人
yaco
基本问题——实现二叉树的前序、中序、后序遍历
（递归、非递归，mirros方法）
递归
- 递归方式下的前中后遍历
// 前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
// write your code here
List<Integer> ans = new ArrayList<>();
if(root != null){
ans.add(root.val);
if(root.left != null){
ans.addAll(inorderTraversal(root.left));
}
if(root.right != null){
ans.addAll(inorderTraversal(root.right));
}
}
return ans;
}
// 中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
// write your code here
List<Integer> ans = new ArrayList<>();
if(root != null){
if(root.left != null){
ans.addAll(inorderTraversal(root.left));
}
ans.add(root.val);
if(root.right != null){
ans.addAll(inorderTraversal(root.right));
}
}
return ans;
}
// 后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
// write your code here
List<Integer> ans = new ArrayList<>();
if(root != null) {
if(root.left != null){
ans.addAll(postorderTraversal(root.left));
}
if(root.right != null){
ans.addAll(postorderTraversal(root.right));
}
ans.add(root.val);
}
return ans;
}
}
非递归
- 非递归的方式实现三种遍历
- 前序：用栈来代替系统栈，首先将root压入栈，每次取出栈顶元素的时候，将值加入ans， 弹出的同时，压入root的左右子树，因为要保证先左子树，再右子树，所以因该先压右子树，再压左子树。
- 中序： 同样使用栈，只要栈空或者当前节点的左子树不为空，就不停的压栈，当某个节点没有左子树时，那么出栈，出栈同时加进ans，然后将其右子树入栈，重复相同的操作
- 后序： 前序遍历的顺序为： 中 - 左 - 右， 后序遍历要实现的顺序为 左 - 右 - 中，那么可以按照前序遍历的思路，用一个栈先压成中 - 右 - 左 的顺序，那么依次出栈，就时后序遍历的顺序
- 具体看代码：
// 前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
// write your code here
List<Integer> ans = new ArrayList<>();
if(root != null){
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
root = stack.pop();
ans.add(root.val);
if(root.right != null){
stack.push(root.right);
}
if(root.left != null){
stack.push(root.left);
}
}
}
return ans;
}
// 中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
// write your code here
List<Integer> ans = new ArrayList<>();
if(root != null){
Stack<TreeNode> stack = new Stack<>();
while(!stack.isEmpty() || root != null){
if(root != null){
stack.push(root);
root = root.left;
}else{
root = stack.pop();
ans.add(root.val);
root = root.right;
}
}
}
return ans;
}
// 后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
// write your code here
List<Integer> ans = new ArrayList<>();
if(root != null) {
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> data = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
root = stack.pop();
data.push(root.val);
if(root.left != null){
stack.push(root.left);
}
if(root.right != null){
stack.push(root.right);
}
}
// 将data数据返回
while(!data.isEmpty()){
ans.add(data.pop());
}
}
return ans;
}
Morris遍历
Morris遍历要点：
- 只要当前节点有左孩子，那么就可以访问它两次，如果没有左孩子只会访问一次。
- Morris遍历使用二叉树节点中大量指向null的指针，由Joseph Morris 于1979年发明。
时间复杂度：O(n)
额外空间复杂度：O(1)
一张图理解Morris遍历路线
Morris遍历
通用的Morris遍历路线入上图所示：
首先不停的向左子树搜索，连接出所有的路径，等到了最左边的子节点，开始不停的向右走，一边走一边关闭之前开辟的路径。
// 基础莫里斯遍历（没有添加遍历元素的添加）
public List<Integer> Morris(TreeNode root){
List<Integer> ans = new ArrayList<>();
if(root != null) {
TreeNode cur1 = root; // 记录当前遍历的节点
TreeNode cur2 = null; // 记录当前节点的左子节点
while(cur1 != null){
cur2 = cur1.left;
if(cur2 != null){
// 一直向右搜索，直到空或者回到了原始位置结束
while(cur2.right != null && cur2.right != cur1){
cur2 = cur2.right;
}
// 如果沿着cur2一直找到了空，表示为第一次遍历，那么连接到开始遍历的地方，且cur2继续向左走，去连接下面的节点
if(cur2.right == null){
cur2.right = cur1; // cur1和cur2连接
cur1 = cur1.left;
continue;
}else{
cur2.right = null;
}
}
cur1 = cur1.right;
}
}
return ans;
}
在基础的Morris代码块之上，按照遍历要求填入不同的操作, 前序，中序，后序分别如下：
- 前序遍历：
前序遍历的顺序是完全按照Mrris找连接点的顺序来的，所以在断开连接的时候已经进行了二次访问，一定不可加操作，若以在cur2找到连接点或者cur2为null的时候加操作。
总结下来记录数据的操作有两处： - 每次cur1指针左移之前
- 如果cur2 == null时，才cur1右移之前
// Morris前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
// write your code here
List<Integer> ans = new ArrayList<>();
if(root != null){
TreeNode cur1 = root;
TreeNode cur2 = null;
while(cur1 != null){
cur2 = cur1.left;
if(cur2 != null){
while(cur2.right != null && cur2.right != cur1){
cur2 = cur2.right;
}
if(cur2.right == null){
cur2.right = cur1;
ans.add(cur1.val);
cur1 = cur1.left;
continue;
}else{
cur2.right = null;
}
}else{
ans.add(cur1.val);
}
cur1 = cur1.right; // 入座left为null，或者cur2断开连接了，一直向右走
}
}
return ans;
}
中序遍历：
- 观察遍历顺序可知，中序遍历的顺序和cur1向右走的顺序完全一致，所以只需要在cur1右移之前添加到结果集就行
总结下来记录数据的操作只有一处： - 每次cur2右移之前
// Morris中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
// write your code here
List<Integer> ans = new ArrayList<>();
if(root != null){
TreeNode cur1 = root;
TreeNode cur2 = null;
while(cur1 != null){
cur2 = cur1.left;
if(cur2 != null){
while(cur2.right != null && cur2.right != cur1){
cur2 = cur2.right;
}
if(cur2.right == null){
cur2.right = cur1;
cur1 = cur1.left;
continue;
}else{
cur2.right = null;
}
}
ans.add(cur1.val);
cur1 = cur1.right; // 入座left为null，或者cur2断开连接了，一直向右走
}
}
return ans;
}
后序遍历：
-
最难的就是后序遍历了，给一张图理解后序遍历的路线。
后序遍历
-
如果，他是按照右子树构成的链表逆序打印，那么只要当cur2进行断连接的时候，逆序打印cur1的left
-
例如：
当cur1在2的位置，cur2此时即将断开4-2之间的连接，那么逆序打印4
当cur1在1的位置，cur2此时即将断开5-1之间的连接，那么逆序打印2 - 5
当cur1在3的位置，cur2此时即将断开6-3之间的连接，那么逆序打印6
最后循环结束的时候，逆序打印 1 - 3 - 7, 完成逆序打印。
// Morris后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
// write your code here
List<Integer> ans = new ArrayList<>();
if(root != null){
TreeNode cur1 = root;
TreeNode cur2 = null;
while(cur1 != null){
cur2 = cur1.left;
if(cur2 != null){
while(cur2.right != null && cur2.right != cur1){
cur2 = cur2.right;
}
if(cur2.right == null){
cur2.right = cur1;
cur1 = cur1.left;
continue;
}else{
cur2.right = null;
helper(ans,cur1.left);
}
}
cur1 = cur1.right; // 入座left为null，或者cur2断开连接了，一直向右走
}
helper(ans,root);
}
return ans;
}
// 逆序添加节点到ans
private void helper(List<Integer> ans, TreeNode root){
TreeNode cur = reverseTree(root);
TreeNode temp = cur;
while(temp != null){
ans.add(temp.val);
temp = temp.right;
}
reverseTree(cur);
}
// 写一个反转链表的方法
private TreeNode reverseTree(TreeNode root){
TreeNode pre = null;
TreeNode next = null;
while(root != null){
next = root.right;
root.right = pre;
pre = root;
root = next;
}
return pre;
}
