陈中正的网络日志

Leetcode: Binary Tree Level Order Traversal

题目

https://oj.leetcode.com/submissions/detail/10496925/

分析

树的层次遍历, 唯一的难点在于如何判断两个结点是否在同一层上。

可以除了nodeQue之外,再增加一个depQue, 来记录每个结点的深度。

代码:

class Solution
{
public:
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        queue<TreeNode*> nodeQue;
        queue<int> depQue;
        TreeNode *node;
        int dep;
        int depBefore;
        vector<vector<int>> res;
        vector<int> solution;

        if (!root)
            return res;

        nodeQue.push(root);
        depQue.push(1);
        depBefore = 1;
        while (!nodeQue.empty())
        {
            node = nodeQue.front();
            nodeQue.pop();
            dep = depQue.front();
            depQue.pop();

            if (dep == depBefore)
                solution.push_back(node->val);
            else
            {
                res.push_back(solution);
                depBefore = dep;
                solution.clear();
                solution.push_back(node->val);
            }

            if (node->left)
            {
                nodeQue.push(node->left);
                depQue.push(dep + 1);
            }
            if (node->right)
            {
                nodeQue.push(node->right);
                depQue.push(dep + 1);
            }
        }
        res.push_back(solution);
        return res;
    }
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/38927101

Categories:  OJ题解 

« Leetcode: Binary Tree Level Order Traversal II Leetcode: Decode Ways »