随笔记录

算法-二叉树-判断搜索二叉树

2022-4-10 diaba 笔试题

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;
    }
}