【优选算法】（第三十六篇）

目录

⼆叉树的锯⻮形层序遍历（medium）

题目解析

讲解算法原理

编写代码

⼆叉树的最⼤宽度（medium）

题目解析

讲解算法原理

编写代码

⼆叉树的锯⻮形层序遍历（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给你⼆叉树的根节点root，返回其节点值的锯⻮形层序遍历。（即先从左往右，再从右往左进⾏下⼀层遍历，以此类推，层与层之间交替进⾏）。
⽰例1：

输⼊：root=[3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
⽰例2：
输⼊：root=[1]
输出：[[1]]
⽰例3：
输⼊：root=[]
输出：[]

讲解算法原理

解法（层序遍历）：
算法思路：
在正常的层序遍历过程中，我们是可以把⼀层的结点放在⼀个数组中去的。
既然我们有这个数组，在合适的层数逆序就可以得到锯⻮形层序遍历的结果。

编写代码

c++算法代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), 
right(right) {}
 * };
 */
class Solution
{
public:
 vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
 {
 vector<vector<int>> ret;
 if(root == nullptr) return ret;
 queue<TreeNode*> q;
 q.push(root);
 int level = 1;
 while(q.size())
 {
 int sz = q.size();
 vector<int> tmp;
 for(int i = 0; i < sz; i++)
 {
 auto t = q.front();
 q.pop();
 tmp.push_back(t->val);
 if(t->left) q.push(t->left);
 if(t->right) q.push(t->right);
 }
 // 判断是否逆序
 if(level % 2 == 0) reverse(tmp.begin(), tmp.end());
 ret.push_back(tmp);
 level++;
 }
 return ret;
 }
};

java算法代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution
{
 public List<List<Integer>> zigzagLevelOrder(TreeNode root) 
 {
 List<List<Integer>> ret = new ArrayList<>();
 if(root == null) return ret;
 Queue<TreeNode> q = new LinkedList<>();
 q.add(root);
 int level = 1;
 
 while(!q.isEmpty())
 {
 int sz = q.size();
 List<Integer> tmp = new ArrayList<>();
 for(int i = 0; i < sz; i++)
 {
 TreeNode t = q.poll();
 tmp.add(t.val);
 if(t.left != null) q.add(t.left);
 if(t.right != null) q.add(t.right);
 }
 // 判断是否逆序
 if(level % 2 == 0) Collections.reverse(tmp);
 ret.add(tmp);
 level++;
 }
 return ret;
 }
}

⼆叉树的最⼤宽度（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给你⼀棵⼆叉树的根节点root，返回树的最⼤宽度。树的最⼤宽度是所有层中最⼤的宽度。
每⼀层的宽度被定义为该层最左和最右的⾮空节点（即，两个端点）之间的⻓度。将这个⼆叉树视作与满⼆叉树结构相同，两端点间会出现⼀些延伸到这⼀层的null节点，这些null节点也计⼊⻓度。
题⽬数据保证答案将会在32位带符号整数范围内。⽰例1：

输⼊：root=[1,3,2,5,3,null,9]输出：4
解释：
最⼤宽度出现在树的第3层，宽度为4(5,3,null,9)。⽰例2：

输⼊：root=[1,3,2,5,null,null,9,6,null,7]输出：7
解释：
最⼤宽度出现在树的第4层，宽度为7(6,null,null,null,null,null,7)。

讲解算法原理

解法（层序遍历）：

算法思路：
1. 第⼀种思路（会超过内存限制）：既然统计每⼀层的最⼤宽度，我们优先想到的就是利⽤层序遍历，把当前层的结点全部存在队列⾥
⾯，利⽤队列的⻓度来计算每⼀层的宽度，统计出最⼤的宽度。但是，由于空节点也是需要计算在内的。因此，我们可以选择将空节点也存在队列⾥⾯。
这个思路是我们正常会想到的思路，但是极端境况下，最左边⼀条⻓链，最右边⼀条⻓链，我们需要存⼏亿个空节点，会超过最⼤内存限制。
2. 第⼆种思路（利⽤⼆叉树的顺序存储-通过根节点的下标，计算左右孩⼦的下标）：依旧是利⽤层序遍历，但是这⼀次队列⾥⾯不单单存结点信息，并且还存储当前结点如果在数组中存
储所对应的下标（在我们学习数据结构-堆的时候，计算左右孩⼦的⽅式）。
这样我们计算每⼀层宽度的时候，⽆需考虑空节点，只需将当层结点的左右结点的下标相减再加 1 即可。
但是，这⾥有个细节问题：如果⼆叉树的层数⾮常恐怖的话，我们任何⼀种数据类型都不能存下下标的值。但是没有问题，因为
• 我们数据的存储是⼀个环形的结构；
• 并且题⽬说明，数据的范围在 int 这个类型的最⼤值的范围之内，因此不会超出⼀圈；
• 因此，如果是求差值的话，我们⽆需考虑溢出的情况。

编写代码

c++算法代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), 
right(right) {}
 * };
 */
class Solution
{
public:
 int widthOfBinaryTree(TreeNode* root) 
 {
 vector<pair<TreeNode*, unsigned int>> q; // ⽤数组模拟队列
 q.push_back({root, 1});
 unsigned int ret = 0;
 while(q.size())
 {
 // 先更新这⼀层的宽度
 auto& [x1, y1] = q[0];
 auto& [x2, y2] = q.back();
 ret = max(ret, y2 - y1 + 1);
 // 让下⼀层进队
 vector<pair<TreeNode*, unsigned int>> tmp; // 让下⼀层进⼊这个队列 for(auto& [x, y] : q)
 {
 if(x->left) tmp.push_back({x->left, y * 2});
 if(x->right) tmp.push_back({x->right, y * 2 + 1});
 }
 q = tmp;
 }
 return ret;
 }
};

java算法代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution
{
 public int widthOfBinaryTree(TreeNode root) 
 {
 List<Pair<TreeNode, Integer>> q = new ArrayList<>(); // ⽤数组模拟队列 q.add(new Pair<TreeNode, Integer>(root, 1));
 int ret = 0; // 记录最终结果
 while(!q.isEmpty())
 {
 // 先更新⼀下这⼀层的宽度
 Pair<TreeNode, Integer> t1 = q.get(0);
 Pair<TreeNode, Integer> t2 = q.get(q.size() - 1);
 ret = Math.max(ret, t2.getValue() - t1.getValue() + 1);
 // 让下⼀层进队
 List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
 for(Pair<TreeNode, Integer> t : q)
 {
 TreeNode node = t.getKey();
 int index = t.getValue();
 if(node.left != null)
 {
 tmp.add(new Pair<TreeNode, Integer>(node.left, index * 2));
 }
 if(node.right != null)
 {
 tmp.add(new Pair<TreeNode, Integer>(node.right, index * 2
+ 1));
 }
 }
 q = tmp;
 }
 return ret;
 }
}