Created
February 8, 2018 16:52
-
-
Save yc0/5aa77b7ab4bac615794034fd452b5814 to your computer and use it in GitHub Desktop.
662. Maximum Width of Binary Tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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. | |
When seeing "full binary tree", I though of traits of binary tree. | |
For example, 2^h-1 nodes for perfect binary tree and each level has 2^(h-1) nodes | |
So following the idea...Let's do implement, and the below implementation took 8ms only at top 100% | |
*/ | |
/** | |
* Definition for a binary tree node. | |
* type TreeNode struct { | |
* Val int | |
* Left *TreeNode | |
* Right *TreeNode | |
* } | |
*/ | |
type Width struct { | |
T *TreeNode | |
W int | |
} | |
func widthOfBinaryTree(root *TreeNode) int { | |
if root == nil { | |
return 0 | |
} | |
q := make([]*Width,0) | |
max := 0 | |
q = append(q, &Width{root, 1}) | |
for len(q) > 0 { | |
n := len(q) | |
_max := q[n-1].W-q[0].W+1 | |
if max < _max { | |
max = _max | |
} | |
nxt := make([]*Width,0) | |
for _,w := range q { | |
v := w.W | |
if w.T.Left != nil { | |
nxt = append(nxt,&Width{w.T.Left,v*2}) | |
} | |
if w.T.Right != nil { | |
nxt = append(nxt,&Width{w.T.Right,v*2+1}) | |
} | |
} | |
q = nxt | |
} | |
return max | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment