leetcode 102. 二叉树的层次遍历

题目描述:

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

[
  [3],
  [9,20],
  [15,7]
]

思路:根据返回结果来看,是需要把每一层单独作为一个vector。层序遍历本身不难,难点在于如何确定层与层的分界线。一个很自然的想法是,用特殊符号作为标记,当在队列中访问到这个元素,就代表这一层结束了,要开始下一层了。既然队列中的元素都是指针,那这个特殊元素就用NULL吧。普通的层序遍历算法是单层循环,而我们的算法应该是二重循环,外循环用于给树分层,内循环用于层内的遍历。代码如下:

    vector<vector<int>> levelOrder(TreeNode* root) {
        //特殊情况
        if(root==NULL) return vector<vector<int>>();
        //需要一个辅助队列q和一个用于保存结果的向量
        queue<TreeNode*> q;
        vector<vector<int>> r;
        //初值,第一层只有root和用于分层的NULL
        q.push(root);
        q.push(NULL);
        while(true)
        {
            vector<int> v;
            //当队首元素,也就是下一个要访问的元素不是NULL
            //说明还在层内,要继续往下访问
            while(q.front())
            {
                root=q.front();
                q.pop();
                v.push_back(root->val);
                if(root->left) q.push(root->left);
                if(root->right) q.push(root->right);
            }
            //下一个元素是NULL,也就是这一层访问结束了
            //先把这一层构造的向量加入结果
            r.push_back(v);
            //然后把队首的NULL去掉
            q.pop();
            //如果此时队列为空,说明遍历结束了,可以返回结果了
            //如果此时队列不为空,说明刚才的访问添加了一层节点,那么在队尾加上NULL作为层分界线。
            if(q.size()) q.push(NULL);
            else return r;
        }
    }

每个节点都只访问一次,时间复杂度 O(n)。由于是二叉树,某一层中的节点数量最多也不会超过n/2,所以队列辅助空间最多用    n/2,空间复杂度O(n)。测试运行时间 4ms。

;

Popular Programs