package com.jiucaiyuan.net.algrithm.tree;



import java.util.Stack;



/**

 * 二叉树的遍历（前序、中序、后续遍历）递归+非递归

 *

 * @Author jiucaiyuan  2022/4/9 22:16

 * @mail services@jiucaiyuan.net

 */

public class PreInPostTraversal {

    /**

     * 先序遍历-非递归

     */

    public static void preOrderUnRecur(Node root) {

        System.out.print("pre-order:");

        if (root != null) {

            Stack<Node> stack = new Stack<>();

            stack.push(root);

            while (!stack.isEmpty()) {

                root = stack.pop();

                System.out.print(root.value + " ");

                //注意：先压right，再压left

                if (root.right != null) {

                    stack.push(root.right);

                }

                if (root.left != null) {

                    stack.push(root.left);

                }

            }

            System.out.println();

        }

    }



    /**

     * 中序遍历-非递归

     * 处理过程：指定root节点的整棵树左边树进栈，弹出时打印，针对弹出节点右树重复该节点的左树进栈

     */

    public static void inOrderUnRecur(Node root) {

        System.out.print("in-order:");

        if (root != null) {

            Stack<Node> stack = new Stack<>();

            while (!stack.isEmpty() || root != null) {

                //不停的把左边树进栈

                if (root != null) {

                    stack.push(root);

                    root = root.left;

                } else {

                    //如果没有左树了，弹出，处理该节点的右子树（再次进入while时还是处理该节点的左边树进栈）

                    root = stack.pop();

                    System.out.print(root.value + " ");

                    root = root.right;

                }

            }

            System.out.println();

        }

    }



    /**

     * 后序遍历-非递归

     * 借助类似前序遍历搞定：准备两个栈，通过类似前序遍历时，该访问时不访问，

     * 直接加入辅助栈，所有的都处理完，再弹出辅助栈进行处理

     */

    public static void postOrderUnRecur(Node root) {

        System.out.print("post-order:");

        if (root != null) {

            Stack<Node> stack = new Stack<>();

            Stack<Node> help = new Stack<>();

            stack.push(root);

            while (!stack.isEmpty()) {

                root = stack.pop();

//                System.out.print(root.value + " ");

                help.push(root);

                //注意：先压left，再压right

                if (root.left != null) {

                    stack.push(root.left);

                }

                if (root.right != null) {

                    stack.push(root.right);

                }

            }

            while (!help.isEmpty()) {

                System.out.print(help.pop().value + " ");

            }

            System.out.println();

        }

    }



    /**

     * 后序遍历-非递归

     */

    public static void postOrderUnRecur2(Node root) {

        System.out.print("post-order:");

        if (root != null) {

            Stack<Node> stack = new Stack<>();

            stack.push(root);

            Node c = null;

            while (!stack.isEmpty()) {

                c = stack.peek();

                if (c.left != null && root != c.left && root != c.right) {

                    stack.push(c.left);

                } else if (c.right != null && root != c.right) {

                    stack.push(c.right);

                } else {

                    System.out.print(stack.pop().value + " ");

                    root = c;

                }

            }

            System.out.println();

        }

    }

    //------------------------------------------------



    /**

     * 遍历序

     *

     * @param root

     */

    public static void f(Node root) {

        //1

        if (root == null) {

            return;

        }

        //1

        f(root.left);

        //2

        //2

        f(root.right);

        //3

        //3

    }



    /**

     * 先序遍历-递归

     */

    public static void preOrderRecur(Node root) {

        if (root == null) {

            return;

        }

        System.out.print(root.value + " ");

        preOrderRecur(root.left);

        preOrderRecur(root.right);

    }



    /**

     * 中序遍历-递归

     */

    public static void inOrderRecur(Node root) {

        if (root == null) {

            return;

        }

        inOrderRecur(root.left);

        System.out.print(root.value + " ");

        inOrderRecur(root.right);

    }



    /**

     * 后序遍历-递归

     */

    public static void postOrderRecur(Node root) {

        if (root == null) {

            return;

        }

        postOrderRecur(root.left);

        postOrderRecur(root.right);

        System.out.print(root.value + " ");

    }



}