如何检查所有叶子是否都位于二叉树的左侧

Question

我一直在为我的讲师发布的考试准备任务而烦恼。如果不是他 "own" 接受完美二叉树的定义，这个问题会相对容易解决。

我的任务是这样的：“检查任何给定的二叉树是否完整（完整 = 除了最后一层之外的所有内容都需要完整 AND 在最后一层所有的叶子都需要在树的左边。写一个 pointer 实现。所以树下面是一个 Complete/Perfect tree 在他的定义中。

互联网上几乎所有关于完美树或完整树的信息都没有解决“所有叶子都需要在左侧”的特定要求。

到目前为止我所做的是编写一个 class 来获取给定树中的节点总数，并将其与基于完美树公式的预期数量进行比较（Math.pow (2, 深度)-1))

这是我的代码：

private int numberOfNodes =0;


public void printLevelorder(){
    LinkedBlockingQueue<BinaryNode<E>> stack = new LinkedBlockingQueue<BinaryNode<E>>();
    BinaryNode<E> node = root;
    stack.offer(node);
    while( !stack.isEmpty()){
        node = stack.poll();
        if( node != null){
            if( node.getLeft() != null){
                stack.offer(node.getLeft());
            }if( node.getRight() != null){
                stack.offer(node.getRight());
            }
            numberOfNodes++;
            System.out.print(node.toString()+ " ");
        }

        else{

            return;
        }


    }
    System.out.println();
}
public int getMaxDepth(BinaryNode<E> node){
    int l =0, r =0;
    if( node != null){
        if( node.getLeft() != null){
            l = getMaxDepth(node.getLeft());
        }if( node.getRight() != null){
            r = getMaxDepth(node.getRight());
        }
    }
    return 1 + Math.max(l,r);
}

public boolean isComplete(){
    return isComplete(root);

}

private boolean isComplete(BinaryNode<E> node){

    int depth = this.getMaxDepth(node);
 int expectedNodes = (int)(Math.pow(2,depth)-1);
 System.out.println( numberOfNodes + "  -  " + expectedNodes);


return false;
}

Answer 1

我从你的问题中了解到，你只需要 check for a complete binary tree 从根开始进行级别顺序遍历。

在遍历过程中，一旦找到一个不是全节点的节点（如果左右children都不为空，则该节点为全节点 ), 后面的节点都必须是叶子节点。

如果一个节点左child为空，那么右child一定为空

Answer 2

基于@poorvank_bhatia 发送的非常有用的 link，我在 java 中的解决方案是：

public void printPostorder(BinaryNode node){
    if( node == null) return;
    printPostorder(node.getLeft());
    printPostorder(node.getRight());
    System.out.print(node.toString()+ " ");
    numberOfNodes++;        
}

public int getNumberOfNodes(){
    return numberOfNodes;           
}

public boolean isComplete(){
    return isComplete(root,0);

}

public boolean isComplete(BinaryNode node, int index){
    if( node == null) return true;

    if( index >= numberOfNodes) return false;

    return (isComplete(node.getLeft(), 2*index +1) 
            && isComplete(node.getRight(),2*index +2));

}

如何检查所有叶子是否都位于二叉树的左侧

How to check if all leaves are positioned to the left side of the BinaryTree

binary-tree