Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- 662. 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).
- 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).
- Note: Answer will in the range of 32-bit signed integer.
- */
- /**
- * Definition for a binary tree node.
- * type TreeNode struct {
- * Val int
- * Left *TreeNode
- * Right *TreeNode
- * }
- */
- type TreeNodeWithNumber struct {
- Node *TreeNode
- Val int
- }
- func widthOfBinaryTree(root *TreeNode) int {
- if root == nil {
- return 0
- }
- q := []*TreeNodeWithNumber{&TreeNodeWithNumber{root, 1}}
- _max := 0
- for len(q) > 0 {
- _max = max(_max, q[len(q)-1].Val-q[0].Val+1)
- nxt := []*TreeNodeWithNumber{}
- for _, tn := range q {
- t := tn.Node
- v := tn.Val
- if t.Left != nil {
- nxt = append(nxt, &TreeNodeWithNumber{t.Left, v*2})
- }
- if t.Right != nil {
- nxt = append(nxt, &TreeNodeWithNumber{t.Right, v*2+1})
- }
- }
- q = nxt
- }
- return _max
- }
- func max(a , b int) int {
- if a > b {
- return a
- }
- return b
- }
Add Comment
Please, Sign In to add comment