LeetCode : 662. Maximum Width of Binary Tree 最大二叉树宽度

水深无声 2021-06-12 20:36 339阅读 0赞

**试题：**  
Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

Example 1:

Input:

1
         /   \
        3     2
       / \     \  
      5   3     9

Output: 4  
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).  
Example 2:

Input:

1
         /  
        3    
       / \       
      5   3

Output: 2  
Explanation: The maximum width existing in the third level with the length 2 (5,3).  
Example 3:

Input:

1
         / \
        3   2 
       /        
      5

Output: 2  
Explanation: The maximum width existing in the second level with the length 2 (3,2).  
Example 4:

Input:

1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7

Output: 8  
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

**代码：**  
首先想到要获得宽度，需要知道当前每个节点所在的位置，位置计算可以参考堆排 2n+1,2n+2；然后为了计算同一层次所有节点，需要一个level来记录当前节点层次，并使用非递归遍历二叉树。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class MarkNode{
        TreeNode node;
        int level, pos;
        MarkNode(TreeNode n, int l, int p){
            node = n;
            level = l;
            pos = p;
        }
    }
    
    class Solution {
        public int widthOfBinaryTree(TreeNode root) {
            Queue<MarkNode> queue = new LinkedList<>();
            queue.offer(new MarkNode(root, 1, 0));
            int curLevel = 1, left = 0, max = 0;
            while(!queue.isEmpty()){
                MarkNode curNode = queue.poll();
                if(curNode.level != curLevel){
                    curLevel = curNode.level;
                    left= curNode.pos;
                }else{
                    max = Math.max(max, curNode.pos - left + 1);
                }
                if(curNode.node.left != null){
                    queue.offer(new MarkNode(curNode.node.left, curNode.level + 1, curNode.pos * 2 + 1));
                }
                if(curNode.node.right != null){
                    queue.offer(new MarkNode(curNode.node.right, curNode.level + 1, curNode.pos * 2 + 2));
                }
            }
            return max;
        }
    
    }