05 August 2008
算上上一层来的null最宽的层数
BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
}
}
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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));
}