二元樹的最大寬度系列問題

作者：Grey

原文地址：

求樹的最大寬度

題目描述

給你一棵二元樹的根節點 root ，返回樹的最大寬度。
樹的最大寬度是所有層中最大的寬度。
每一層的寬度被定義為該層最左和最右的非空節點（即，兩個端點）之間的長度。
將這個二元樹視作與滿二元樹結構相同，兩端點間會出現一些延伸到這一層的 null 節點，這些 null 節點也計入長度。

題目連結：LeetCode 662. Maximum Width of Binary Tree

主要思路

由於求寬度的時候，可以把這個二元樹視作滿二元樹，所以在原先的 TreeNode 基礎上，封裝一個資料結構

    static class AnnotateNode {
        TreeNode treeNode;
        int depth;
        int pos;

        public AnnotateNode(TreeNode treeNode, int depth, int pos) {
            this.treeNode = treeNode;
            this.depth = depth;
            this.pos = pos;
        }
    }

這個資料結構增加了兩個資料項：

depth：表示一個 TreeNode 節點在第幾層。

pos：表示一個 TreeNode 節點在當前層排第幾（注：空節點也算）。

以一顆二元樹舉例，如下範例圖，以兩個節點來說明封裝的 AnnotateNode，虛線節點是 null 節點。

對於一棵滿二元樹來說，如果當前節點是 depth，pos，那麼其左孩子就是 depth + 1，pos * 2；右孩子就是 depth + 1，pos * 2 + 1。

接下來，並把每個位置的 pos，depth 指標記錄到 AnnotateNode 節點中。

參考二元樹的按層遍歷對二元樹進行遍歷，在下一層開始結算上一層的結果。

而且每次要記錄上一層的最左位置 left，在一層結束時，記錄一個最右側位置 right，然後設定一個全域性最大的 max，max 的更新策略就是

max = Math.max(max, right - left + 1)

完整程式碼見

class Solution {
        public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int max = 1;
        Queue<AnnotateNode> queue = new LinkedList<>();
        queue.offer(new AnnotateNode(root, 0, 0));
        int curDepth = 0;
        int left = 0;
        while (!queue.isEmpty()) {
            AnnotateNode node = queue.poll();
            if (node.treeNode != null) {
                queue.offer(new AnnotateNode(node.treeNode.left, node.depth + 1, node.pos * 2));
                queue.offer(new AnnotateNode(node.treeNode.right, node.depth + 1, node.pos * 2 + 1));
                if (curDepth != node.depth) {
                    curDepth = node.depth;
                    left = node.pos;
                }
                int right = node.pos;
                max = Math.max(max, right - left + 1);
            }
        }
        return max;
    }

    static class AnnotateNode {
        TreeNode treeNode;
        int depth;
        int pos;

        public AnnotateNode(TreeNode treeNode, int depth, int pos) {
            this.treeNode = treeNode;
            this.depth = depth;
            this.pos = pos;
        }
    }
}

求樹的最大寬度的有效節點個數

題目描述

給定一個二元樹，你需要編寫一個函數來獲取這課樹的最大寬度，二元樹的最大寬度是指具有節點數最多的那一層的結點個數。

題目連結見：牛客-二元樹的最大寬度

與上一個問題不同，本題求的最大寬度是有效節點的個數，所以是不包括 null 節點的。

主要思路

可以使用雜湊表，並且按照層次遍歷的方法，存下每一層的節點個數。不過還有更省空間的做法，設定有限幾個變數，無需申請一個雜湊表

// 當前層的結尾節點，初始為 head 
TreeNode curEnd = head;
// 下一層的結尾節點，初始為 null
TreeNode nextEnd = null;
// 當前層的節點個數，初始化為 0
int curLevelNodes = 0;

然後也是二元樹的按層遍歷對二元樹進行遍歷，遍歷過程中，如果遍歷到的當前節點 c 滿足 c == curEnd，即：當前節點就是當前結尾位置的節點，則可以確定一層結束，更新全域性 max，當前層節點個數歸零，即 curLevelNodes = 0，並將下層結尾節點賦值給 curEnd。

max = Math.max(curLevelNodes, max);
curLevelNodes = 0;
curEnd = nextEnd;

完整程式碼見

public class Solution {

   public  int getMaxWidth(TreeNode head) {
        if (head == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        int max = 1;
        queue.offer(head); 
        TreeNode curEnd = head;
        TreeNode nextEnd = null;
        int curLevelNodes = 0;
        while (!queue.isEmpty()) {
            TreeNode c = queue.poll();
            if (c.left != null) {
                queue.offer(c.left);
                nextEnd = c.left;
            }
            if (c.right != null) {
                queue.offer(c.right);
                nextEnd = c.right;
            }
            curLevelNodes++;
            // 當前節點已經到結束了
            if (c == curEnd) {
                max = Math.max(curLevelNodes, max);
                curLevelNodes = 0;
                curEnd = nextEnd;
            }
        }
        return max;
    }
}

演演算法和資料結構筆記

二元樹的最大寬度系列問題

二元樹的最大寬度系列問題

求樹的最大寬度

求樹的最大寬度的有效節點個數

更多