662. 二叉树最大宽度
查看题目中等
树
二叉树
低频
解法一：深度优先遍历
时间复杂度： | 空间复杂度： | 推荐使用
动画演示
准备就绪 - 输入二叉树结构，然后点击开始
代码实现
class Solution {
Map<Integer, Integer> map = new HashMap<>();
int ans;
public int widthOfBinaryTree(TreeNode root) {
dfs(root, 1, 0);
return ans;
}
void dfs(TreeNode root, int u, int depth) {
if (root == null) return ;
if (!map.containsKey(depth)) map.put(depth, u);
ans = Math.max(ans, u - map.get(depth) + 1);
u = u - map.get(depth) + 1;
dfs(root.left, u << 1, depth + 1);
dfs(root.right, u << 1 | 1, depth + 1);
}
}时间复杂度：
空间复杂度：