Java判断二叉树是否平衡

Question

这是“破解编码面试”中的问题:

Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.

书中只给出了递归的解决方案。我想出了一个使用 BFS 的迭代解决方案，只是想分享它。我进行了试运行，但想确保我没有犯错。我还想看看其他人认为他们可以如何改进它。

谢谢!

Answer 1

class Node
{
int data;
LinkedList<Node> children;
}

public static boolean isBalanced(Node root)
{
LinkedList<Node> queue = new LinkedList<Node>();
queue.offer(root);

int currentLevel = -1, toNextLevel = 0, toNextLevelTemp = 1;

int minLevel = Integer.MAX_VALUE, maxLevel = Integer.MIN_VALUE;

while(!queue.isEmpty())
{
    if(toNextLevel == 0)
    {
        currentLevel++;
        toNextLevel = toNextLevelTemp;
        toNextLevelTemp = 0;
    }

    Node temp = queue.poll();
    toNextLevel--;

    //if temp is a leaf, record its depth
    if(temp.children.size() == 0)   
    {
        if(currentLevel < minLevel)
            minLevel = currentLevel;

        if(currentLevel > maxLevel)
            maxLevel = currentLevel;
    }

    //do whatever with temp
    for(Node child: temp.children)
    {
        queue.add(child);
        toNextLevelTemp++;
    }
}

//if difference between minLevel and maxLevel is more than 1
if(maxLevel - minLevel > 1)
    return false;

return true;
}