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).
Solution: DFS
Let us assign an id to each node, similar to the index of a heap. root is 1, left child = parent * 2, right child = parent * 2 + 1. Width = id(right most child) – id(left most child) + 1, so far so good.
However, this kind of id system grows exponentially, it overflows even with long type with just 64 levels. To avoid that, we can remap the id with id – id(left most child of each level).
Time complexity: O(n)
Space complexity: O(h)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: int widthOfBinaryTree(TreeNode* root) { vector<int> ids; // left most id of each level. function<int(TreeNode*, int, int)> dfs = [&](TreeNode* node, int d, int id) -> int { if (!node) return 0; if (d == ids.size()) ids.push_back(id); return max({id - ids[d] + 1, dfs(node->left, d + 1, (id - ids[d]) * 2), dfs(node->right, d + 1, (id - ids[d]) * 2 + 1)}); }; return dfs(root, 0, 0); } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { private List<Integer> ids; public int widthOfBinaryTree(TreeNode root) { this.ids = new ArrayList<Integer>(); return dfs(root, 0, 0); } private int dfs(TreeNode root, int d, int id) { if (root == null) return 0; if (ids.size() == d) ids.add(id); return Math.max(id - ids.get(d) + 1, Math.max(this.dfs(root.left, d + 1, (id - ids.get(d)) * 2), this.dfs(root.right, d + 1, (id - ids.get(d)) * 2 + 1))); } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 |
# Author: Huahua class Solution: def widthOfBinaryTree(self, root: TreeNode) -> int: ids = [] def dfs(node: TreeNode, d: int, id: int) -> int: if not node: return 0 if d == len(ids): ids.append(id) return max(id - ids[d] + 1, dfs(node.left, d + 1, (id - ids[d]) * 2), dfs(node.right, d + 1, (id - ids[d]) * 2 + 1)) return dfs(root, 0, 0) |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment