算法通关：017_2：二叉树及三种顺序的非递归遍历

文章目录

题目
思路
运行结果

题目

二叉树及三种顺序的非递归遍历

思路

在这里插入图片描述

import java.util.Stack;/*** @Author: ggdpzhk* @CreateTime: 2024-08-04* 二叉树非递归版本*/
public class _017_Tree2 {public static void main(String[] args) {TreeNode head = new TreeNode(1);head.left = new TreeNode(2);head.right = new TreeNode(3);head.left.left = new TreeNode(4);head.left.right = new TreeNode(5);head.right.left = new TreeNode(6);head.right.right = new TreeNode(7);System.out.println("先序遍历非递归版");preOrder(head);System.out.println();System.out.println("中序遍历非递归版");inOrder(head);System.out.println();System.out.println("后序遍历非递归版：两个栈");postOrder(head);System.out.println();System.out.println("后序遍历非递归版：1个栈");postOrder2(head);System.out.println();}public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}//先序打印所有节点，非递归版public static void preOrder(TreeNode head) {if(head != null){Stack<TreeNode> stack = new Stack<TreeNode>();stack.push(head);//压入顺序先右再左  这样弹出顺序就是反的，就是我们要的先序遍历的顺序//不懂你就写一遍 这个思路真的很牛while(!stack.isEmpty()){head = stack.pop();System.out.print(head.val + " ");if(head.right != null){stack.push(head.right);}if(head.left != null){stack.push(head.left);}}System.out.println();}}//中序打印所有节点，非递归版public static void inOrder(TreeNode head) {if(head != null){//这个是rootStack<TreeNode> stack = new Stack();//下面的这个head是相对的根节点while(!stack.isEmpty() || head != null){//栈不为空 或者当前子树不为空        （ 比如左边界最后一个点 子树就为空，但是栈里还有东西，就还会进whil）if(head != null){//子树左边界全部进栈stack.push(head);head = head.left;}else{//栈弹出一个节点，打印//弹出节点为head，对右子树 左边界进栈head = stack.pop();System.out.print(head.val + " ");head = head.right;}}System.out.println();}}//后序打印所有节点，非递归版//这是用两个栈的方法/*算法：先 ：中 右 左（出栈才嫩实现正确顺序）先`：中 左 右（调换出栈顺序）后 ：左 右 中（把 先` 出栈顺序反转），那就是 让先`进后栈再出栈*/public static void postOrder(TreeNode head) {if(head != null){Stack<TreeNode> stack = new Stack();Stack<TreeNode> collect = new Stack();stack.push(head);while(!stack.isEmpty()){head = stack.pop();//出栈再进栈collect.push(head);//将其输出即可if(head.left != null){stack.push(head.left);}if(head.right != null){stack.push(head.right);}}//此时已全部进collect栈，将其输出while(!collect.isEmpty()){//栈嘛，输出就没了，不用++System.out.print(collect.pop().val+" ");}}System.out.println();}//后序打印所有节点，非递归版//这是用1个栈的方法//先处理左右字数，再返回网上。h是哨兵//                       左子树==h说明左边已经处理完，该处理右子树//                       右子树==h说明左右子树都处理完，往上走，回到相对的根节点public static void postOrder2(TreeNode h) {if(h != null){Stack<TreeNode> stack = new Stack();stack.push(h);//如果始终没有打印过节点，h就一直是root头节点//一旦打印过节点，h就变成打印节点//之后h的含义：上一次打印的节点while(!stack.isEmpty()){TreeNode cur = stack.peek();if(cur.left != null&& h != cur.left&& h != cur.right){//有左树且左树没处理过stack.push(cur.left);}else if(cur.right != null&& h != cur.right){//有右树且右树没处理过stack.push(cur.right);}else {//左树，右树都没有 或者 都处理完了System.out.print(cur.val+" ");h = stack.pop();}}System.out.println();}}
}