二叉树所有层中最多的节点个数和最大宽度

本文主要是介绍二叉树所有层中最多的节点个数和最大宽度，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

求二叉树所有层中最多的节点个数

解题思路：根据题意可知，要想获得二叉树中每一层的节点个数，需要对二叉树进行层序遍历，并在层序遍历的过程中记录每一层具有多少个节点。因此可以在层序遍历每一个节点的时候为每个节点分配一个层数的记录。层序遍历的方法通常是使用队列进行，首先将头节点加入到队列中，如果头节点不为空，将队列中的第一个元素弹出，这个被弹出的元素的左子节点不为空则将左子节点加入到队列中；如果右节点不为空则将右子节点加入到队列中。但是层序遍历的过程中并没有统计每一个节点到底属于哪一层的信息，因此需要将节点与节点所属层数信息进行绑定。这里可以借用一个辅助类构造一个辅助节点，将节点和节点所属层数作为成员变量。每次入队列和出队列的时候直接对这个辅助节点进行操作即可。判断该节点所在的层数和当前层数是否相同，如果相同则将该层的个数进行加1，如果不同，则将该层的节点个数设置为0，当前层加1，进行重新计数。
代码如下：

public static int getMaxNumOfNodes(Node root) {
    if (root == null) {
        return 0;
    }
    Queue<AnotateNode> queue = new LinkedList<>();
    // 将头节点加入到队列中
    queue.offer(new AnotateNode(root, 1));
    // 当前节点层数
    int curLevel = 1;
    // 当前层的节点个数
    int numNodes = 0;
    // 由于头节点不为空，所以最大节点个数至少为1
    int maxNodes = 1;
    while (!queue.isEmpty()) {
        AnotateNode aNode = queue.poll();
        int nodeLevel = aNode.levels;
        if (curLevel == nodeLevel) {
            numNodes++;
        } else {
        	// 新的一层开始，更新前一层的最大节点数信息
            maxNodes = Math.max(maxNodes, numNodes);
            curLevel = nodeLevel;
            numNodes = 1;
        }
        if (aNode.node.left != null) {
            queue.offer(new AnotateNode(aNode.node.left, aNode.levels + 1));
        }

        if (aNode.node.right != null) {
            queue.offer(new AnotateNode(aNode.node.right, aNode.levels + 1));
        }
    }
    maxNodes = Math.max(numNodes, maxNodes);
    return maxNodes;
}


class Node {
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
    }
}

class AnotateNode {
    int levels;
    Node node;
    public AnotateNode(Node node, int levels) {
        this.levels = levels;
        this.node = node;
    }
}

求二叉树的最大宽度(leetcode 662)

解题思路：也是按照层序遍历的思路，与求所有层最多节点个数不同的是，当第三层的节点为[v1,v2,null,v4]时，最多节点个数是3，而最大宽度是4。因此可以使用双端队列的方式，为每一个节点构造一个辅助节点，将节点与节点在当前层的位置绑定在一起，因此在每次入栈或者出栈的过程中，就获得了当前节点的位置信息。由于使用的是双端队列，因此可以通过队列头和队列尾获得当前层的最大宽度。那么如何统计下一层的位置信息呢，这里采用左子节点是父节点的位置的2倍，即（2 * postion）；左子节点是父节点的2别+1，即（2 * position + 1）。当左右节点不为空的时候将节点和其位置信息加入。当每一层节点遍历结束时，更新最大宽度。
代码如下：

public static int maxWidth(Node root) {
    if (root == null) {
        return 0;
    }
    // 创建双端队列
    Deque<AuxiliaryNode> deque = new LinkedList<>();
    // 将头节点加入
    deque.offer(new AuxiliaryNode(root, 0));
    
    int maxWidth = 0;
    while (!deque.isEmpty()) {
    maxWidth = Math.max(maxWidth, deque.peekLast().position - deque.peekFirst().position + 1);
        int size = deque.size();
        while (size > 0) {
        
            AuxiliaryNode curANode = deque.poll();
            Node curNode = curANode.node;
            int curPosition = curANode.position;

            if (curNode.left != null) {
                deque.offer(new AuxiliaryNode(curNode.left, 2 * curPosition));
            }

            if (curNode.right != null) {
                deque.offer(new AuxiliaryNode(curNode.right, 2 * curPosition + 1));
            }
            
            size--;
        }
    }
    return maxWidth;

}

class Node {
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
    }
}

class AuxiliaryNode {
    int position;
    Node node;
    public AuxiliaryNode(Node node, int position) {
        this.node = node;
        this.position = position;
    }
}

这篇关于二叉树所有层中最多的节点个数和最大宽度的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！