LeetCode 662. 二叉樹最大寬度

截止到目前我已經寫了 500多道演算法題，其中部分已經整理成了pdf檔案，目前總共有1000多頁（并且還會不斷的增加），大家可以免費下載
下載鏈接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取碼：6666

每一行從最左邊到最右邊我們很容易想到的就是二叉樹的BFS遍歷，他就是一層一層遍歷的，關于二叉樹的BFS不明白的可以看下下面的視頻，

視頻鏈接

所以這題思路很容易想到，就是遍歷每一層的時候計算這一層最左邊節點到最右邊節點的距離，大致代碼如下

public int widthOfBinaryTree(TreeNode root) {
    if (root == null)
        return 0;
    //使用雙端佇列
    Deque<TreeNode> queue = new LinkedList<>();
    //把根節點加入到佇列中
    queue.offer(root);
    //記錄最大的寬度
    int maxWide = 0;
    while (!queue.isEmpty()) {
        //當前層節點的數量
        int levelCount = queue.size();
        // int gap = 當前層最左邊到最右邊的距離
        maxWide = Math.max(maxWide, gap);
        //遍歷當前層的所有節點，把他們的子節點在加入到佇列中
        for (int i = 0; i < levelCount; i++) {
            TreeNode node = queue.poll();
            //如果左子節點不為空，就把左子節點加入到佇列中
            if (node.left != null) {
                queue.offer(node.left);
            }
            //如果右子節點不為空，就把右子節點加入到佇列中
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    return maxWide;
}

他就是從上往下一層一層遍歷的，遍歷每一層的時候我們需要計算當前層的最大距離，保留最大的即可，這里關鍵是怎么計算當前層的最大距離，

我們可以這樣來計算，把它想象成為一顆滿二叉樹，假如根節點是遍歷的第1個節點，那么他的兩個子節點分別是遍歷的第2個和第3個節點，并且可以推算出如果一個節點是第n個遍歷的，那么他的兩個子節點分別是第n*2和n*2+1個遍歷的，具體我們來畫個圖看一下

我們可以把這些值存到一個map中，也可以把它直接存到節點中，這里我們就把他存到節點中，在遍歷每一層的時候用當前層最右邊的值減去最左邊的值+1就是當前層的最大距離，來看下最終代碼，

public int widthOfBinaryTree(TreeNode root) {
    if (root == null)
        return 0;
    //使用雙端佇列
    Deque<TreeNode> queue = new LinkedList<>();
    //把根節點加入到佇列中
    queue.offer(root);
    //根節點的值我們把它修改為1
    root.val = 1;
    //記錄最大的寬度
    int maxWide = 0;
    while (!queue.isEmpty()) {
        //當前層節點的數量
        int levelCount = queue.size();
        //當前層最左邊節點的值
        int left = queue.peekFirst().val;
        //當前層最右邊節點的值
        int right = queue.peekLast().val;
        //當前層的最大寬度就是right - left + 1，
        //這里計算之后要保留最大的
        maxWide = Math.max(maxWide, right - left + 1);
        //遍歷當前層的所有節點，把他們的子節點在加入到佇列中
        for (int i = 0; i < levelCount; i++) {
            TreeNode node = queue.poll();
            int position = node.val;
            //如果左子節點不為空，就把左子節點加入到佇列中
            if (node.left != null) {
                node.left.val = position * 2;
                queue.offer(node.left);
            }
            //如果右子節點不為空，就把右子節點加入到佇列中
            if (node.right != null) {
                node.right.val = position * 2 + 1;
                queue.offer(node.right);
            }
        }
    }
    return maxWide;
}

這里因為左邊節點先入隊，所以peekFirst()回傳的就是當前層最左邊的節點，右邊節點是最后入隊的，所以peekLast()回傳的是當前層最右邊的節點，

//記錄最大的寬度
int maxWide = 0;

public int widthOfBinaryTree(TreeNode root) {
    dfs(root, 0, 1, new ArrayList<>(), new ArrayList<>());
    return maxWide;
}

/**
 * @param root
 * @param level    遍歷到第幾層
 * @param position 每個節點在滿二叉樹中的位置
 * @param left     只記錄最左邊的節點，每層只記錄一個
 * @param right    只記錄遍歷過的最右邊節點，每層只記錄一個（這里是遍歷過的，如果當前層有更右邊的節點，
 *                 會把當前層的替換）
 */
public void dfs(TreeNode root, int level, int position, List<Integer> left, List<Integer> right) {
    if (root == null)
        return;
    //首次到當前層，要把當前值分別加入到left和right中
    if (left.size() == level) {
        left.add(position);
        right.add(position);
    } else {//如果當前層已經遍歷過，會替換掉
        right.set(level, position);
    }
    //遞回遍歷下一層的左右子節點
    dfs(root.left, level + 1, position << 1, left, right);
    dfs(root.right, level + 1, position * 2 + 1, left, right);
    //計算當前層的最大間距，保留最大值
    maxWide = Math.max(maxWide, right.get(level) - left.get(level) + 1);
}