频道栏目
首页 > 考试 > 其他 > 正文
LeetCode103. Binary Tree Zigzag Level Order Traversal题解
2017-03-22 09:55:33         来源:SYSU_LBY的博客  
收藏   我要投稿

1. 题目描述

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (IE, from left to right, then right to left for the next level and alternate between).

2. 样例

Given binary tree [3,9,20,null,null,15,7],
这里写图片描述
return its zigzag level order traversal as:
这里写图片描述

3. 分析

题目的意思是:层次遍历一棵二叉树,然后把每一层的节点存进一个vector里面,将每一层的vector存进一个大的vector里面,最终返回。其中每一层的vector有这样的要求:需要进行折线形存储,即上一层是从左至右存储节点元素,则下一层是从右至左存储节点元素。
最近博客更新的几篇题解都是讲解树的层次遍历的各种变形的,这次也不例外,无非是存储的时候玩了点花样。
思路也比较好想:仍然用队列FIFO进行层次遍历,访问整棵树,每一层用一个局部vector变量everyLevel存储每一层的节点数值,只不过每到新的一层,进行判断:如果当前层数是偶数(根节点设为第0层),那么说明上一层数是奇数,需要将everyLevel进行逆置操作。判断新的一层的算法也用的轻车熟路:设置两个变量current_levellast_level一起遍历,当前者大于后者时,说明到了新的一层。
这里写图片描述

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector > zigzagLevelOrder(TreeNode* root) {
        vector >result;
        vector everyLevel;
        queuenode;
        queuelevel;
        int current_level = 0;
        int last_level = 0;
        TreeNode *current_node = root;
        if (root != NULL) {
            node.push(current_node);
            level.push(current_level);
            while(!node.empty()) {
                current_level = level.front();
                current_node = node.front();
                level.pop();
                node.pop();
                if (current_level > last_level) {
                    last_level = current_level;
                    if (current_level % 2 == 0) {
                        reverse(everyLevel.begin(), everyLevel.end());
                    }
                    result.push_back(everyLevel);
                    everyLevel.clear();
                    everyLevel.push_back(current_node->val);
                }
                else {
                    everyLevel.push_back(current_node->val);
                }
                if (current_node->left != NULL) {
                    node.push(current_node->left);
                    level.push(current_level+1);
                }
                if (current_node->right != NULL) {
                    node.push(current_node->right);
                    level.push(current_level+1);
                }
            }
            if (current_level % 2 != 0) {
                reverse(everyLevel.begin(), everyLevel.end());
            }
            result.push_back(everyLevel);
        }
        return result;
    }
};

5. 心得

刚开始第一提交错误,卡在了第27个测试样例上面:
这里写图片描述
原因是这样的,我没有考虑边界情况。在我的算法中:我是判断current_level为偶数,说明上一层是奇数,进行逆转,从而再将其加入result里面。
然而只有2层的二叉树,根节点为0层,第1层的情况来不及在判断条件里面执行,程序就会跳出循环,造成只有2层的二叉树没有执行1层的逆序操作,所以我在最后面补了一个判断条件以及相应的逆序操作,才通过了测试。

点击复制链接 与好友分享!回本站首页
上一篇:LeetCode 240. Search a 2D Matrix II 解题报告
下一篇:编程开发习题:120*n
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站