662. 二叉树最大宽度

Chenyi_li / 2023-08-18 / 原文

662. 二叉树最大宽度

BFS ，也就是广度优先遍历，类似层次遍历的方法（同上给每个节点编上号），求得每一层，把每一层的左右两端的编号进行相减。

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        Map<TreeNode,Integer> map = new HashMap<>();//存储节点对应的下标
        Queue<TreeNode> queue = new LinkedList<>();//通过队列实现bfs
        //初始化
        int max = 1;
        zixun(root);
        map.put(root,1);
        while (!queue.isEmpty()) {
            int start = map.get(queue.peek());//获取每层起始节点（即最左端点）的下标
            int size = queue.size();
            while (size > 0) {
                TreeNode node = queue.poll();
                size--;
                int index = map.get(node);//获取此节点下标，用与给其的左右孩子确定下标
                if (node.left != null) {
                    map.put(node.left,index*2);//确定左孩子下标
                    queue.offer(node.left);//节点入队
                }
                if (node.right != null) {
                    map.put(node.right,index*2 + 1);//确定右孩子下标
                    queue.offer(node.right);//节点入队
                }
                if(size == 0) max = Math.max(max,index - start + 1);//本层遍历结束，更新层宽最大值
            }
        }
        return max;
    }
}

DFS深度优先遍历，通过递归的方式实现，递归每层的记录带上层数，进行计算。

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);
    }
}

链接：https://leetcode.cn/problems/maximum-width-of-binary-tree/solutions/1778862/by-ac_oier-33er/
来源：力扣（LeetCode）