LeetCode 102.Binary Tree Level Order Traversal (二叉树的层次遍历)

落日映苍穹つ 2022-05-09 04:56 137阅读 0赞

题目描述：

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

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

3
       / \
      9  20
        /  \
       15   7

返回其层次遍历结果：

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

AC C++ Solution:

递归：

队列：

/**
     * 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<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int> > res;
            
            if(!root)   return res;
            
            queue<TreeNode*> q;
            q.push(root);
            q.push(NULL);
            vector<int> cur_vec;
            
            while(!q.empty()) {
                TreeNode *t = q.front();
                q.pop();
                
                if(t == NULL) {
                    res.push_back(cur_vec);
                    cur_vec.resize(0);
                    if(q.size() > 0)
                        q.push(NULL);       //每层之间用一个NULL作为分隔符
                }
                else {                      //把每个节点的值存入cur_vec,并把下一层的节点加入队列
                    cur_vec.push_back(t->val);  
                    if(t->left) q.push(t->left);
                    if(t->right) q.push(t->right);
                }
            }
            return res;
        }
    };

--------------------