java - 重构代码查找二叉树是否为 BST

Question

我已经编写了代码来查找给定的树是否是 BST。但我需要帮助重构它。我正在寻找的一些东西是：

1. 摆脱临时变量（如 Martin Fowler 所建议）
2. 结合 leftTreeMax 和 RightTreeMin 方法
3. 更好的方法名称

另外，我会感谢人们提出的任何其他重构想法。

package com.cc.bst;

import com.cc.queue.Queue;
import com.cc.trees.BinaryTreeNode;

public class IsBinaryTreeBST {

public static boolean binaryTreeBST ( BinaryTreeNode root) {

    if (root == null) {
        return false;
    }
    int maxVal = leftTreeMax(root.getLeft());
    int minVal = rightTreeMin(root.getRight());
    int rootVal = root.getData();

    if (maxVal == 0 || minVal == 0 ) {
        return false;
    }

    if (rootVal > maxVal && rootVal < minVal) {
        return true;
    }

    return false;

}

private static int leftTreeMax (BinaryTreeNode node) {

    if (node == null) {
        return 0;
    }
    Queue nodeQueue = new Queue();
    nodeQueue.enqueue(node);
    int maxValue = node.getData();

    while (!nodeQueue.isEmpty()) {
        BinaryTreeNode tempNode = (BinaryTreeNode) nodeQueue.dequeue();         
        BinaryTreeNode left = tempNode.getLeft();
        BinaryTreeNode right = tempNode.getRight();

        if (left != null ) {
            if (left.getData() > tempNode.getData()) {
                return 0;
            }
            nodeQueue.enqueue(left);
        }
        if (right != null) {
            if ( tempNode.getData() > right.getData()) {
                return 0;
            }
            nodeQueue.enqueue(right);
        }
        if (tempNode.getData() > maxValue) {
            maxValue = tempNode.getData();
        }           
    }       
    System.out.println("---------- maxVal -------->" +  maxValue);
    return maxValue;
}

private static int rightTreeMin(BinaryTreeNode node) {

    if (node == null) {
        return 0;
    }
    Queue nodeQueue = new Queue();
    nodeQueue.enqueue(node);
    int minValue = node.getData();

    while (!nodeQueue.isEmpty()) {
        BinaryTreeNode tempNode = (BinaryTreeNode) nodeQueue.dequeue();         
        BinaryTreeNode left = tempNode.getLeft();
        BinaryTreeNode right = tempNode.getRight();
        System.out.println("---------- tempNode -------->" + tempNode.getData());

        if (left != null ) {
            System.out.println("---------- left -------->" + left.getData());

            if (left.getData() > tempNode.getData()) {
                return 0;
            }
            nodeQueue.enqueue(left);                
        }
        if (right != null) {
            if ( tempNode.getData() > right.getData()) {
                return 0;
            }
            System.out.println("---------- right -------->" + right.getData());

            nodeQueue.enqueue(right);               
        }           
        if (tempNode.getData() < minValue) {
            minValue = tempNode.getData();
        }
    }       
    System.out.println("---------- minVal -------->" +  minValue);

    return minValue;
        }
}

Answer 1

老实说，我很惊讶您的代码如此复杂。我很难找到进行一轮改进的原因：重写它似乎更简单。可以这样想：

我们需要满足 3 条规则，（取自维基百科）：

1. 节点的左子树仅包含键小于节点键的节点。
2. 节点的右子树仅包含键大于或等于节点键的节点。
3. 左右子树也必须是二叉搜索树。

如您所见，规则 3 给您一个很大的提示，即递归是有序的，因为每个子树都需要与其父树具有相同的规则。

那么为什么不做这样的事情：

checkBST(node,min,max) {
    if(node == NULL)
        return true
    if(node.value < min || node.value >= max)
        return false
    return checkBST(left,min,node.value) && checkBST(right,node.value,max)
}

checkBST(root,-infinity,+infinity)

这样，您正在为每个子树保留其值的边界，该边界由其父级接收，因此现在假设左子树需要小于其父级，则其父级为最大值这个子树可以是，右子树也一样，它必须大于或等于它的父树。

这个算法不是最好的时间复杂度，但最容易编写和理解。