package com.jiucaiyuan.net.algrithm.tree;



import java.util.Stack;



/**

 * <pre>

 * 【问题】判断一棵树是否是搜索二叉树（Binary Search Tree），（又：二叉搜索树，二叉排序树）

 * 【概念】搜索二叉树：树的左子树比头结点小，右子树比头结点大（左子<头<右子）

 * 【思路】通过二叉树的中序遍历，判断树中节点一直是升序的，不出现降序即可

 * </pre>

 *

 * @Author jiucaiyuan  2022/4/10 16:42

 * @mail services@jiucaiyuan.net

 */



public class IsBST {



    /**

     * 判断是搜索二叉树（递归套路实现）

     *

     * @param root

     * @return

     */

    public static boolean isBst(Node<Integer> root) {

        return process(root).isBst;

    }



    /**

     * <pre>

     * 使用二叉树递归套路来处理

     * 1.基本case处理

     * 2.询问左子树结果

     * 3.询问右子树结果

     * 4.处理当前节点是否满足，返回最终结果

     * </pre>

     *

     * @param x

     * @return

     */

    public static ResultData process(Node<Integer> x) {

        if (x == null) {

            //如果返回ResultData，最大值和最小值不好设置，所以返回null，分情况处理

            return null;

        }

        ResultData leftResult = process(x.left);

        ResultData rightResult = process(x.right);

        //组织返回结果使用

        int minValue = x.value;

        int maxValue = x.value;

        if (leftResult != null) {

            minValue = Math.min(minValue, leftResult.minValue);

            maxValue = Math.max(maxValue, leftResult.maxValue);

        }

        if (rightResult != null) {

            minValue = Math.min(minValue, rightResult.minValue);

            maxValue = Math.max(maxValue, rightResult.maxValue);

        }

        //当前是否符合搜索二叉树条件

        boolean isBst = true;

        if (leftResult != null && (!leftResult.isBst || leftResult.maxValue >= x.value)) {

            isBst = false;

        }

        if (rightResult != null && (!rightResult.isBst || x.value >= rightResult.minValue)) {

            isBst = false;

        }

        return new ResultData(isBst, minValue, maxValue);

    }



    static class ResultData {

        boolean isBst;

        int minValue;

        int maxValue;



        ResultData(boolean isBst, int min, int max) {

            isBst = isBst;

            minValue = min;

            maxValue = max;

        }

    }



    //中序遍历实现，每次递归比较之前处理的值

    private static int preValue = Integer.MIN_VALUE;



    /**

     * 中序遍历-递归

     */

    public static boolean isBstRecur(Node<Integer> root) {

        if (root == null) {

            return true;

        }

        //左是否是搜索二叉树

        boolean isLeftBst = isBstRecur(root.left);

        if (!isLeftBst) {

            return false;

        }

        //如果当前节点不大于前一个处理的值，非搜索二叉树

        if (root.value <= preValue) {

            return false;

        } else {

            //记录前一个处理的值

            preValue = root.value;

        }

        //判断右是否是搜索二叉树

        return isBstRecur(root.right);

    }



    /**

     * 中序遍历-非递归

     * 处理过程：指定root节点的整棵树左边树进栈，判断是否满足搜索二叉树，针对弹出节点右树重复该节点的左树进栈

     */

    public static boolean isBstUnRecur(Node<Integer> root) {

        if (root != null) {

            int preValue = Integer.MIN_VALUE;

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

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

                //不停的把左边树进栈

                if (root != null) {

                    stack.push(root);

                    root = root.left;

                } else {

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

                    root = stack.pop();

                    if (root.value <= preValue) {

                        return false;

                    } else {

                        preValue = root.value;

                    }

                    root = root.right;

                }

            }

        }

        return true;

    }

}