Leetcode - Maximum Width of Binary Tree

https://leetcode.com/problems/maximum-width-of-binary-tree/

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).

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func widthOfBinaryTree(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue := []*TreeNode{root}
    result := 0
    for len(queue) != 0 {
        size := len(queue)
        var first int
        var last int
        for first = 0; first < size; first++ {
            node := queue[first]
            if node != nil {
                break
            }
        }
        if first >= size {
            break
        }
        for last = size-1; last >= first; last-- {
            node := queue[last]
            if node != nil {
                break
            }
        }
        for i := first; i <= last; i++ {
            node := queue[i]
            if node != nil {
                queue = append(queue, node.Left)
                queue = append(queue, node.Right)
            } else {
                queue = append(queue, nil)
                queue = append(queue, nil)
            }
        }
        result = max(result, last - first+ + 1)
        queue = queue[size:]
    }
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

• 相关文章
• 全局相关文章