https://leetcode.com/problems/maximum-width-of-binary-tree
http://www.voidcn.com/article/p-fvunixcy-bnv.html
https://segmentfault.com/a/1190000017149507
https://leetcode.com/problems/maximum-width-of-binary-tree/discuss/106645/cjava-bfsdfs3liner-clean-code-with-explanation
X. BFS
BFS: using dequeue
https://leetcode.com/problems/maximum-width-of-binary-tree/discuss/106663/Java-O(n)-BFS-one-queue-clean-solution
https://leetcode.com/articles/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).X. DFS
http://www.voidcn.com/article/p-fvunixcy-bnv.html
实现的思路是用两个hashmap保存当前层的index， minMap保存当前层最左边的节点的index， maxMap则保存最后边的节点的index。 minMap每一层只需要存储一次，（第一次）, maxMap 则需要不断的更新，因为不确定当前的点是否是最右侧的。 最后统计一下每一层的最大值。如果不存在最大或者最小值，那么就跳过这一层。
public int widthOfBinaryTree(TreeNode root) {
if(root == null) return 0;
HashMap<Integer, Integer> minMap = new HashMap<>();
HashMap<Integer, Integer> maxMap = new HashMap<>();
dfs(minMap, maxMap, root, 0, 0);
int max = Integer.MIN_VALUE;
for(int i=0;i<maxMap.size();i++) {
if(!maxMap.containsKey(i) || !minMap.containsKey(i)) continue;
max = Math.max(max, maxMap.get(i) - minMap.get(i));
}
return max;
}
private void dfs(HashMap<Integer, Integer> minMap,
HashMap<Integer, Integer> maxMap,
TreeNode node,
int layer, int index) {
if(node == null) return;
if(!minMap.containsKey(layer)) minMap.put(layer, index);
if(!maxMap.containsKey(layer)
|| maxMap.get(layer)<index) {
maxMap.put(layer, index);
}
if(node.left != null) {
dfs(minMap, maxMap, node.left, layer+1, index*2);
}
if(node.right != null) {
dfs(minMap, maxMap, node.right, layer+1, index*2+1);
}
}
We know that a binary tree can be represented by an array (assume the root begins from the position with index
1 in the array). If the index of a node is i, the indices of its two children are 2*i and 2*i + 1. The idea is to use two arrays (start[] and end[]) to record the the indices of the leftmost node and rightmost node in each level, respectively. For each level of the tree, the width isend[level] - start[level] + 1. Then, we just need to find the maximum width.
Java version:
public int widthOfBinaryTree(TreeNode root) {
return dfs(root, 0, 1, new ArrayList<Integer>(), new ArrayList<Integer>());
}
public int dfs(TreeNode root, int level, int order, List<Integer> start, List<Integer> end){
if(root == null)return 0;
if(start.size() == level){
start.add(order); end.add(order);
}
else end.set(level, order);
int cur = end.get(level) - start.get(level) + 1;
int left = dfs(root.left, level + 1, 2*order, start, end);
int right = dfs(root.right, level + 1, 2*order + 1, start, end);
return Math.max(cur, Math.max(left, right));
}https://segmentfault.com/a/1190000017149507
https://leetcode.com/problems/maximum-width-of-binary-tree/discuss/106645/cjava-bfsdfs3liner-clean-code-with-explanation
The idea is to use heap indexing:
1
2 3
4 5 6 7
8 9 x 11 x 13 x 15
Regardless whether these nodes exist:
- Always make the id of left child as
parent_id * 2; - Always make the id of right child as
parent_id * 2 + 1;
So we can just:
- Record the
idofleft most nodeat each level of the tree(you can tell be check the size of the container to hold the first nodes); - At each node, compare the
distancefrom it the left most node with the currentmax width;
public int widthOfBinaryTree(TreeNode root) {
List<Integer> lefts = new ArrayList<Integer>(); // left most nodes at each level;
int[] res = new int[1]; // max width
dfs(root, 1, 0, lefts, res);
return res[0];
}
private void dfs(TreeNode node, int id, int depth, List<Integer> lefts, int[] res) {
if (node == null) return;
if (depth >= lefts.size()) lefts.add(id); // add left most node
res[0] = Integer.max(res[0], id + 1 - lefts.get(depth));
dfs(node.left, id * 2, depth + 1, lefts, res);
dfs(node.right, id * 2 + 1, depth + 1, lefts, res);
} Map<Integer, int[]> map = new HashMap<>();
public int widthOfBinaryTree(TreeNode root) {
if (root == null) return 0;
findMax(root, 0, 0);
int res = 1;
for (int[] rec : map.values()) {
res = Math.max(res, rec[1] - rec[0] + 1);
}
return res;
}
private void findMax(TreeNode root, int level, int pos) {
if (root == null) return;
int[] rec = map.get(level);
if (rec == null) {
rec = new int[2];
rec[0] = Integer.MAX_VALUE;
rec[1] = Integer.MIN_VALUE;
}
rec[0] = Math.min(rec[0], pos);
rec[1] = Math.max(rec[1], pos);
map.put(level, rec);
findMax(root.left, level + 1, 2 * pos);
findMax(root.right, level + 1, 2 * pos + 1);
}X. BFS
BFS: using dequeue
https://leetcode.com/problems/maximum-width-of-binary-tree/discuss/106663/Java-O(n)-BFS-one-queue-clean-solution
change the val of node to be the index to save space. The value is useless. All we need is just the index.
this is a bit intrusive by changing the treenode val, right?
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
root.val = 0;
int max = 1;
while (!queue.isEmpty()) {
int size = queue.size();
max = Math.max(max, queue.peekLast().val - queue.peekFirst().val + 1);
for (int i = 0; i < size; i++) {
root = queue.poll();
if (root.left != null) {
root.left.val = root.val * 2;
queue.offer(root.left);
}
if (root.right != null) {
root.right.val = root.val * 2 + 1;
queue.offer(root.right);
}
}
}
return max;
}https://leetcode.com/articles/maximum-width-of-binary-tree/
public int widthOfBinaryTree(TreeNode root) {
Queue<AnnotatedNode> queue = new LinkedList();
queue.add(new AnnotatedNode(root, 0, 0));
int curDepth = 0, left = 0, ans = 0;
while (!queue.isEmpty()) {
AnnotatedNode a = queue.poll();
if (a.node != null) {
queue.add(new AnnotatedNode(a.node.left, a.depth + 1, a.pos * 2));
queue.add(new AnnotatedNode(a.node.right, a.depth + 1, a.pos * 2 + 1));
if (curDepth != a.depth) {
curDepth = a.depth;
left = a.pos;
}
ans = Math.max(ans, a.pos - left + 1);
}
}
return ans;
}
}
class AnnotatedNode {
TreeNode node;
int depth, pos;
AnnotatedNode(TreeNode n, int d, int p) {
node = n;
depth = d;
pos = p;
}
}
public int widthOfBinaryTree(TreeNode root) {
if (root == null) return 0;
int max = 0;
Queue<Map.Entry<TreeNode, Integer>> q = new LinkedList<Map.Entry<TreeNode, Integer>>();
q.offer(new AbstractMap.SimpleEntry(root, 1));
while (!q.isEmpty()) {
int l = q.peek().getValue(), r = l; // right started same as left
for (int i = 0, n = q.size(); i < n; i++) {
TreeNode node = q.peek().getKey();
r = q.poll().getValue();
if (node.left != null) q.offer(new AbstractMap.SimpleEntry(node.left, r * 2));
if (node.right != null) q.offer(new AbstractMap.SimpleEntry(node.right, r * 2 + 1));
}
max = Math.max(max, r + 1 - l);
}
return maxwidth;
}
public int widthOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>(); // 用于树的广度优先遍历。
Queue<Integer> queuePos = new LinkedList<>(); // 用于保存上面队列中树节点对应的位置标号。
queue.add(root);
queuePos.add(1);// 在顶层跟结点位置为1.
int countCurrent = 1;// 记录正在遍历的当前层次的剩余数量。
int countTmp = 0; // 记录下一层次结点的数量。
int max = countCurrent; // 记录最大的差距。（目标）（与start 和 end相关）
int start = 1;// 记录某层次结点的最左边的结点。
int end = 1;// 记录某层次结点的最右边的结点。
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
end = queuePos.poll();
if (current.left != null) {
queue.add(current.left);
queuePos.add(2 * end);// 分配左孩子结点的序号。
countTmp++;// 记录下层结点的数量
}
if (current.right != null) {
queue.add(current.right);
queuePos.add(2 * end + 1); // 分配右孩子结点的序号
countTmp++;
}
// 当前层次已遍历完毕，计算max,并且为下一层次的遍历准备。
if (--countCurrent == 0) {
// 目标比对。
if (max < end - start + 1) {
max = end - start + 1;
}
countCurrent = countTmp;// 设置下一层次剩余的数量
countTmp = 0;
// 设置下一层结点的start.
start = queuePos.isEmpty() ? 1 : queuePos.peek();
}
}
return max;
}
