二叉树的层次遍历

algorithm

二叉树定义

struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

层次遍历的实现

• 层次遍历从左到右，从上到下
• 从左到右，左边先进先出
• 非常容易想到使用一个队列来实现
• 问题是，如何扩展队列，以及如何判断一层的开始和结束？

 vector<int> tree_level_order_traverse(TreeNode* root) {
        if(root == nullptr)
            return {};
        queue<TreeNode*> que;
        que.push(root);
        vector<int> res;
        while(!que.empty()) {
            int size = que.size();
            for(int i =0 ;i < size; i++) {
                TreeNode *n = que.front();
                que.pop();
                res.push_back(n->val);
                if(n->left)
                    que.push(n->left);
                if(n->right)
                    que.push(n->right);
            }
        }
        return res;
    }

相关题目

• 1
• 2
• 3
• 4
• 5