leetcode：103二叉树的锯齿形遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -100 <= Node.val <= 100

步骤1：问题定义与分析

这是一道二叉树的层序遍历变体问题，具有以下特点：

• 输入：二叉树的根节点
• 输出：二维数组，表示锯齿形层序遍历结果
• 特殊要求：相邻层的遍历方向相反（先从左到右，再从右到左，如此交替）
• 限制条件：
  • 节点数范围：[0, 2000]
  • 节点值范围：[-100, 100]
• 边界情况：
  • 空树
  • 只有一个节点的树
  • 完全二叉树
  • 非对称的二叉树

步骤2：算法设计与分析

最优解决方案：使用广度优先搜索（BFS）配合层次标记

1. 使用队列进行层序遍历
2. 用一个布尔变量记录当前层的遍历方向
3. 每一层的节点值存入临时数组，根据方向决定是否翻转

时间复杂度分析：

• BFS遍历所有节点：O(n)
• 某些层需要翻转：最坏情况O(n)
• 总体时间复杂度：O(n)

空间复杂度：O(n)，队列存储节点

步骤3：代码实现

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;  // 存储最终结果
        if (!root) return result;    // 处理空树情况
        
        queue<TreeNode*> q;         // 用于BFS的队列
        q.push(root);
        bool leftToRight = true;    // 控制遍历方向的标志
        
        while (!q.empty()) {
            int levelSize = q.size();  // 当前层的节点数
            vector<int> currentLevel(levelSize);  // 存储当前层的节点值
            
            // 处理当前层的所有节点
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                
                // 根据方向决定节点值在当前层数组中的位置
                int index = leftToRight ? i : (levelSize - 1 - i);
                currentLevel[index] = node->val;
                
                // 将下一层的节点加入队列
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
            result.push_back(currentLevel);  // 将当前层添加到结果中
            leftToRight = !leftToRight;      // 切换方向
        }
        
        return result;
    }
};

步骤4：解题启发

这道题目给我们的启发：

1. 在处理树结构时，层序遍历是一个强大的工具
2. 使用标志位可以优雅地处理交替模式
3. 通过控制插入位置，可以避免额外的数组翻转操作
4. 边界条件的处理对于保证代码健壮性很重要

步骤5：实际应用

这种锯齿形遍历算法在实际中有很多应用场景：

1. 文件系统可视化：

   • 在文件浏览器中展示目录结构时，可以使用这种交错展示方式来节省水平空间
   • 例如：Windows资源管理器的树状视图可以采用这种方式来优化显示效果

2. 网络拓扑展示：

   • 在网络监控系统中展示网络设备的层级关系
   • 交错展示可以减少视觉混乱，使网络结构更清晰

具体应用示例： 假设我们正在开发一个组织架构图展示系统：

class OrgChart {
    struct Employee {
        string name;
        vector<Employee*> subordinates;
    };
    
    void displayOrgChart(Employee* ceo) {
        // 使用相同的锯齿形遍历算法
        queue<Employee*> q;
        q.push(ceo);
        bool leftToRight = true;
        
        while (!q.empty()) {
            int levelSize = q.size();
            vector<string> currentLevel;
            
            for (int i = 0; i < levelSize; i++) {
                Employee* emp = q.front();
                q.pop();
                currentLevel.push_back(emp->name);
                
                for (Employee* sub : emp->subordinates) {
                    q.push(sub);
                }
            }
            
            // 根据方向决定是否翻转显示顺序
            if (!leftToRight) {
                reverse(currentLevel.begin(), currentLevel.end());
            }
            
            // 显示当前层级的员工
            displayLevel(currentLevel);
            leftToRight = !leftToRight;
        }
    }
};

这种展示方式可以：

1. 减少视觉混乱
2. 优化空间使用
3. 提高可读性
4. 使组织结构更容易理解

原文地址：https://blog.csdn.net/D2510466299/article/details/144176878

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！