二叉树递归迭代及morris层序前中后序遍历详解

目录

• 分析二叉树的前序，中序，后序的遍历步骤

• 1.层序遍历

• 方法一：广度优先搜索
• 方法二：递归

• 前序遍历--递归

• 前序遍历--迭代

• 核心思想：

• morris--前序遍历

public List<List<Integer>> levelOrder(TreeNode root) {
        //返回的结果
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(null == root){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //根节点入队
        queue.add(root);
        while(!queue.isEmpty()){
            //一层的结果
            List<Integer> level = new ArrayList<Integer>();
            int levelCount = queue.size();
            //添加节点到一层的List中去
            for(int i = 0; i < levelCount ; i ++){
                //节点出队
                TreeNode node = queue.remove();
                //节点的左子树入队
                if(node.left != null){
                  queue.add(node.left);   
                }
                //节点的右子树入队   
                if(node.right != null){
                  queue.add(node.right);   
                }  
                level.add(node.val);
            }
            res.add(level);
        }
        return res;
    }

public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root==null) {
			return res;
		}	
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		//将根节点放入队列中，然后不断遍历队列
		queue.add(root);
		while(queue.size()>0) {
			//获取当前队列的长度，这个长度相当于 当前这一层的节点个数
			int size = queue.size();
			ArrayList<Integer> tmp = new ArrayList<Integer>();
			//将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
			//如果节点的左/右子树不为空，也放入队列中
			for(int i=0;i<size;++i) {
				TreeNode t = queue.remove();
				tmp.add(t.val);
				if(t.left!=null) {
					queue.add(t.left);
				}
				if(t.right!=null) {
					queue.add(t.right);
				}
			}
			//将临时list加入最终返回结果中
			res.add(tmp);
		}
		return res;
}

public List<Integer> preorderTraversal(TreeNode root) {
        //递归
        List<Integer> list = new ArrayList<>();
        preOrder(root,list);
        return list;
    }
    public void preOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        list.add(root.val);
        preOrder(root.left,list);
        preOrder(root.right,list);
}

public List<Integer> inorderTraversal(TreeNode root) {
        //递归
        List<Integer> list = new LinkedList<>();
        inOrder(root,list);
        return list;
    }
    public void inOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        inOrder(root.left,list);
        list.add(root.val);
        inOrder(root.right,list);
}

public List<Integer> postorderTraversal(TreeNode root) {
        //递归
        List<Integer> list = new LinkedList<>();
        postOrder(root,list);
        return list;
    }
    public void postOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        postOrder(root.left,list);
        postOrder(root.right,list);
        list.add(root.val);
}

public List<Integer> preorderTraversal(TreeNode root) {
        //迭代
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        //临时节点，帮助遍历二叉树
        TreeNode node = root;
        //栈的作用是用来短暂的保存遍历节点的值，以助于最后值的返回
        while(!stack.isEmpty() || node != null){
            while(node != null){
                list.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return list;
}

public List<Integer> inorderTraversal(TreeNode root) {
        //迭代
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);//出栈的时候才将父节点 的值加入到结果中
            root = root.right;
        }
        return list;
}

public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> list = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                list.addFirst(root.val);//addFirst():向链表首部添加元素
                root = root.right;
            } else {
                root = stack.pop();
                root = root.left;
            }
        }
        return list;
}

public static void morris(Node head){
    if(head == null){
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while(cur != null){
        //cur有没有左树
        mostRight = cur.left;
        if(mostRight != null){//有左树的情况
            //找到cur左树上，真实的最右节点
            //前者说明是第一次来到当前的cur，后者说明是第二次来到当前的cur
            while(mostRight.right != null && mostRight.right != cur){
                mostRight = mostRight.right;
            }
            //从while中出来，mostRight一定是cur左树上的最右节点
            if(mostRight.right == null){
                mostRight.right = cur;
                cur = cur.left;
                continue;//结束的是外层的循环！！！！！！！！！！！！！
            }else{//走到这里意味着：mostRight.right == cur
                mostRight.right = null;
            }
        }
        //cur没有左树
        cur = cur.right;
    }
}

public static void morrisPre(Node head){
    if(head == null){
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while(cur != null){
        mostRight = cur.left;
        if(mostRight != null){
            while(mostRight.right != null && mostRight.right != cur){
                mostRight = mostRight.right;
            }
            if(mostRight.right == null){
                mostRight.right = cur;
                System.out.print(cur.value + " ");
                cur = cur.left;
                continue;
            }else{
                mostRight.right = null;
            }
        }else{
            System.out.print(cur.value + " ");
        }
        cur = cur.right;
    }
    System.out.println();
}

public static void morrisIn(Node head){
    if(head == null){
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while(cur != null){
        mostRight = cur.left;
        if(mostRight != null){
            while(mostRight.right != null && mostRight.right != cur){
                mostRight = mostRight.right;
            }
            if(mostRight.right == null){
                mostRight.right = cur;
                cur = cur.left;
                continue;
            }else{
                mostRight.right = null;
            }
        }
        System.out.print(cur.value + " ");
        cur = cur.right;
    }
    System.out.println();
}

public static void morrisPos(Node head) {
		if(head == null) {
			return;
		}
		Node cur = head;
		Node mostRight = null;
		while(cur != null) {
			mostRight = cur.left;
			if(mostRight != null) {
				while(mostRight.right != null && mostRight.right != cur) {
					mostRight = mostRight.right;
				}
				if(mostRight.right == null) {
					mostRight.right = cur;
					cur = cur.left;
					continue;
				}else {
					mostRight.right = null;
					printEdge(cur.left);//逆序打印左树的右边界
				}
			}
			cur = cur.right;
		}
		printEdge(head);//最后打印整棵树的右边界
		System.out.println();
	}
 	public static void printEdge(Node head) {
		Node tail = reverseEdge(head);
		Node cur = tail;
		while(cur != null) {
			System.out.print(cur.value + " ");
			cur = cur.right;
		}
		reverseEdge(tail);
	}
	private static Node reverseEdge(Node from) {
		Node pre = null;
		Node next = null;
		while(from != null) {
			next = from.right;
			from.right = pre;
			pre = from;
			from = next;
		}
		return pre;
	}