(第24天)【leetcode题解】二叉树的层序遍历

102、二叉树的层序遍历

题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

思路

1. 层序遍历

就是从根节点一层一层的从左到右遍历

2. 数据结构选择

选择队列这种先入先出的结构来辅助实现

3. 整体算法

从root开始，每遍历到一个节点，在把它放入结果集的同时，把它的子节点按从左到右的顺序加入队列。

代码

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> res;//结果集，是一个二维数组
        while (!que.empty()) {
            int size = que.size();//当前节点的层数有几个节点
            vector<int> vec;//一层的节点值
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node -> val);//把队头节点的值加入到结果集
                //同时把当前节点的左右节点按顺序加入队列
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
            res.push_back(vec);
        }
        return res; 
    }
};

递归法：

class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& res, int depth) {
        if (cur == nullptr) return;//终止条件
        //加入结果集
        if (res.size() == depth) res.push_back(vector<int>());//先加入一层的容器
        res[depth].push_back(cur -> val);//在给这一层加入结果的值(每次递归都必然运行)
        //开始递归
        order(cur -> left, res, depth + 1);
        order(cur -> right, res, depth + 1);
    }

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;//结果集
        int depth = 0;//结果集中存储的节点层数
        order(root, res, depth);
        return res;
    }
};

107、二叉树的层序遍历II

题目描述

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

思路

正序把二叉树层序遍历的结果放入结果集，然后翻转结果集。

代码

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();//当前这一层有几个节点
            vector<int> vec;
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node -> val);
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
            res.push_back(vec);
        }
        reverse(res.begin(), res.end());//翻转
        return res;
    }
};

199、二叉树的右视图

题目描述

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

思路

层序遍历的时候，队列que每次存储一层数据，只要判断当前遍历到的数据是否是这一层最后一个数据即可。

代码

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> res;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();//获得每一层的节点个数
            //进入循环，处理每层的节点数据
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (i == size - 1) res.push_back(node -> val);//遍历到每层的最后一个节点时，把这个节点加入结果集
                if (node -> left) que.push(node -> left);//把当前节点的左子节点加入队列
                if (node -> right) que.push(node -> right);//把当前节点的右子节点加入队列
            }
        } 
        return res;
    }
};

637、二叉树的层平均值

题目描述

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

思路

层序遍历过程中，计算每层节点数据的总和，在计算平均值，把平均值加入结果集。

代码

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> que;
        vector<double> res;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();//每层节点的数目
            double sum = 0;//每层的总值
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                sum += node -> val;
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
            res.push_back(sum / size);//把每层平均值加入结果集
        }
        return res;
    }
};

思考

1. 深度优先遍历的逻辑用栈来实现，先入后出，也就是递归的逻辑
2. 广度优先遍历的逻辑用队列实现，先入先出