查找最大子树（具有最大顶点）（二叉搜索树）

Question

对于给定的二叉搜索树，找到每个非叶顶点满足条件的顶点数最多的最大子树： • 左子树的高度与右子树的高度相差不超过2（绝对值）

public void findMaxBalancedSubtree(KjvNode node, KjvOutPrm oPrm) {
  
        if (node == null) {
            oPrm.height = 0;
            oPrm.maxTree = null;
            oPrm.size = 0;
        } else if (isLeaf(node)) {
            oPrm.maxTree = node;
            oPrm.height = 0;
            oPrm.size = 1;
        } else { //Если не лист и не пустое
            KjvOutPrm lPrm = new KjvOutPrm();
            KjvOutPrm rPrm = new KjvOutPrm();
            findMaxBalancedSubtree(node.getLeft(), lPrm);
            findMaxBalancedSubtree(node.getRight(), rPrm);
            oPrm.height = Math.max(lPrm.height, rPrm.height) + 1;
            boolean isBalanced = Math.abs(lPrm.height - rPrm.height) <= 2;
            oPrm.size = rPrm.size + lPrm.size + 1;
            if (isBalanced) {
              if (lPrm.size > rPrm.size) {
                    oPrm.maxTree = lPrm.maxTree;
                } else {
                    oPrm.maxTree = rPrm.maxTree;
                }
            } else {
                if (lPrm.size > rPrm.size) {
                    oPrm.maxTree = lPrm.maxTree;
                }
                else {oPrm.maxTree = rPrm.maxTree;}
            }
        }
    }

I've tried to write a code but it doesn't give the right answer. For example for the tree 100,91,87,105,80,20,106,104,103,102,107 the right answer is 105. (KjvOutPrm contains KjvNode maxTree, int height, int size):
        KjvTreeInt xTr = new KjvTreeInt();
        xTr.add(100);
        xTr.add(91);
        xTr.add(87);
        xTr.add(105);
        xTr.add(80);
        xTr.add(20);
        xTr.add(106);
        xTr.add(104);
        xTr.add(103);
        xTr.add(102);
        xTr.add(107);
        xTr.printTree();
        KjvNode nd = xTr.findMaxBalancedSubtree();
        System.out.println("maxTree="+nd.getElement());

Much code i can't add because i recieved an error that there is so much code.

Answer 1

代码中的问题在于设置

oPrm.maxTree

的逻辑。您并不总是考虑以

node

为根的当前子树是最大平衡子树。您只查看子子树，这可能会错过以当前节点为根的较大平衡子树。

试试这个：

public void findMaxBalancedSubtree(KjvNode node, KjvOutPrm oPrm) {
    if (node == null) {
        oPrm.height = 0;
        oPrm.maxTree = null;
        oPrm.size = 0;
        return;
    }
    if (isLeaf(node)) {
        oPrm.height = 1;
        oPrm.maxTree = node;
        oPrm.size = 1;
        return;
    }

    KjvOutPrm lPrm = new KjvOutPrm();
    KjvOutPrm rPrm = new KjvOutPrm();
    findMaxBalancedSubtree(node.getLeft(), lPrm);
    findMaxBalancedSubtree(node.getRight(), rPrm);
    
    oPrm.height = Math.max(lPrm.height, rPrm.height) + 1;
    boolean isBalanced = Math.abs(lPrm.height - rPrm.height) <= 2;
    
    oPrm.size = lPrm.size + rPrm.size + 1;
    
    if (isBalanced) {
        oPrm.maxTree = node;
    } else {
        oPrm.maxTree = (lPrm.size > rPrm.size) ? lPrm.maxTree : rPrm.maxTree;
    }
}

注意：我将叶节点的高度更改为1（如果您认为叶节点的高度为0，请恢复此值）。