1+ // 662. 二叉树最大宽度
2+
3+
4+ /**
5+ * Definition for a binary tree node.
6+ * public class TreeNode {
7+ * int val;
8+ * TreeNode left;
9+ * TreeNode right;
10+ * TreeNode() {}
11+ * TreeNode(int val) { this.val = val; }
12+ * TreeNode(int val, TreeNode left, TreeNode right) {
13+ * this.val = val;
14+ * this.left = left;
15+ * this.right = right;
16+ * }
17+ * }
18+ */
19+
20+
21+ /*
22+ 递归：
23+ 1、成员变量最大宽度maxWidth，哈希表map保存每层第一个节点的位置值 {深度:位置}
24+ 2、定义递归函数：
25+ 1）方法功能：入参是节点、深度、位置，从map中获取同深度即同层的第一个节点位置，更新计算最大宽度
26+ 2）终止条件：节点为空时，结束
27+ 3）递归逻辑：左右节点同样需要计算其所在层的宽度，因此调用同样的方法递归处理
28+ */
29+ class Solution {
30+ private int maxWidth = 0 ;
31+ private Map <Integer , Integer > map = new HashMap <>();
32+
33+ public int widthOfBinaryTree (TreeNode root ) {
34+ dfs (root , 0 , 0 );
35+ return maxWidth ;
36+ }
37+
38+ private void dfs (TreeNode root , int depth , int pos ) {
39+ if (root == null ) {
40+ return ;
41+ }
42+ map .computeIfAbsent (depth , key -> pos );
43+ maxWidth = Math .max (maxWidth , pos - map .get (depth ) + 1 );
44+ dfs (root .left , depth + 1 , 2 * pos );
45+ dfs (root .right , depth + 1 , 2 * pos + 1 );
46+ }
47+ }
48+
49+
50+ /*
51+ 迭代：
52+ 1、节点为空时返回0
53+ 2、使用两个队列，节点队列nodeQueue存放节点，位置队列posQueue存放节点的位置值，初始化时加入根节点和位置值到队列中
54+ 3、位置关系：根节点位置为 i，则左节点位置为 2i，有节点位置为 2i+1
55+ 4、层序遍历，记录当前层最左边的位置，遍历更新右边的位置，计算更新当前层宽度，并把下一层的节点和位置值存入队列
56+ 5、每层遍历完后都更新最大宽度，最终得到二叉树的最大宽度
57+
58+ 1
59+ / \
60+ 2 3
61+ */
62+ class Solution {
63+ public int widthOfBinaryTree (TreeNode root ) {
64+ if (root == null ) {
65+ return 0 ;
66+ }
67+ Queue <TreeNode > nodeQueue = new LinkedList <>();
68+ Queue <Integer > posQueue = new LinkedList <>();
69+ nodeQueue .add (root );
70+ posQueue .add (1 );
71+ int maxWidth = 0 ;
72+ while (!nodeQueue .isEmpty ()) {
73+ boolean firstFlag = true ;
74+ int left = -1 , right = -1 , tempWidth = 0 ;
75+ int size = nodeQueue .size ();
76+ while (size > 0 ) {
77+ TreeNode node = nodeQueue .poll ();
78+ int pos = posQueue .poll ();
79+ if (firstFlag ) {
80+ left = pos ;
81+ firstFlag = false ;
82+ }
83+ right = pos ;
84+ tempWidth = Math .max (tempWidth , right - left + 1 );
85+ if (node .left != null ) {
86+ nodeQueue .add (node .left );
87+ posQueue .add (2 * pos );
88+ }
89+ if (node .right != null ) {
90+ nodeQueue .add (node .right );
91+ posQueue .add (2 * pos + 1 );
92+ }
93+ size --;
94+ }
95+ maxWidth = Math .max (maxWidth , tempWidth );
96+ }
97+ return maxWidth ;
98+ }
99+ }
100+
101+
102+ /*
103+ 迭代优化：位置队列posQueue存放的是一层节点的所有位置，直接取最左边和最右边的位置就可以计算当前层的宽度，再更新最大宽度
104+ */
105+ class Solution {
106+ public int widthOfBinaryTree (TreeNode root ) {
107+ if (root == null ) {
108+ return 0 ;
109+ }
110+ LinkedList <TreeNode > nodeQueue = new LinkedList <>();
111+ LinkedList <Integer > posQueue = new LinkedList <>();
112+ nodeQueue .add (root );
113+ posQueue .add (1 );
114+ int maxWidth = 0 ;
115+ while (!nodeQueue .isEmpty ()) {
116+ maxWidth = Math .max (maxWidth , posQueue .peekLast () - posQueue .peekFirst () + 1 );
117+ int size = nodeQueue .size ();
118+ while (size > 0 ) {
119+ TreeNode node = nodeQueue .poll ();
120+ int pos = posQueue .poll ();
121+ if (node .left != null ) {
122+ nodeQueue .add (node .left );
123+ posQueue .add (2 * pos );
124+ }
125+ if (node .right != null ) {
126+ nodeQueue .add (node .right );
127+ posQueue .add (2 * pos + 1 );
128+ }
129+ size --;
130+ }
131+ }
132+ return maxWidth ;
133+ }
134+ }
0 commit comments