二叉樹的最大寬度系列問題
二叉樹的最大寬度系列問題
作者：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;
}
}
