JAVA非递归遍历二叉树

参考 https://blog.csdn.net/xxxxxxxx00772299/article/details/109318495

先序和中序

从node开始不断压入左节点直到拿到最左边的叶子结点，出栈，每次出栈判断右节点是否为空，如果不为空，右节点为node，重复以上步骤。
可以看到，父节点和左节点是连续的，所以可以完成先序和中序，但后序需要一些处理。

• 如果在入栈时进行输出，那么就是先序遍历
• 如果在出栈时进行输出，那么就是中序遍历

两个方法基本相同，唯一差别就在输出位置。
while负责入栈，if负责出栈

	 public static void preShow(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        if(root==null||root.left==null&&root.right==null) return;
        while(!(stack.isEmpty()&&node==null)){
            while(node!=null){
                stack.push(node);
                System.out.println(node);
                node = node.left;
            }
            if(!stack.isEmpty()){
                node = stack.pop();
                node = node.right;
            }
        }
    }
    public static void inShow(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        if(root==null||root.left==null&&root.right==null) return;
        while(!(stack.isEmpty()&&node==null)){
            while(node!=null){
                stack.push(node);
                node = node.left;
            }
            if(!stack.isEmpty()){
                node = stack.pop();
                System.out.println(node);
                node = node.right;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

后序

如果按照上面的方法，在2出栈的后才能拿到3，但后序的顺序是132，所以要保证

• 如果右子树不存在，或者右子树在访问过的情况下（visited），正常输出2。
• 如果右子树存在，并且右子树未访问过，2在栈中，让右节点作为node，进行下一次循环。

代码只对if进行了改动

      public static void postShow(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
//        visited代表已经访问过的右子树
        TreeNode visited = null;
        if(root==null||root.left==null&&root.right==null) return;
        while(!(stack.isEmpty()&&node==null)){
            while(node!=null){
                stack.push(node);
                node = node.left;
            }
            if(!stack.isEmpty()){
                node = stack.pop();
                if (node.right == null||node.right == visited) {
                    System.out.println(node);
//                    此节点已经被访问
                    visited = node;
//                    右子树已经处理完毕或者为null，跳过入栈环节，下一次循环直接父节点出栈
                    node = null;
                }else{
//                    为下一次输出保留这个节点，下一次循环处理右子节点。
                   stack.push(node);
                   node = node.right;
                }

            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28