Day17 二叉树的层序遍历专题

107 二叉树的层序遍历II

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

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if(root != nullptr)
            que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            vector<int> vec;
            while(size--)
            {
                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);
            }
            result.push_back(vec);
        }
        reverse(result.begin(),result.end());  //只多了这一步
        return result;
    }
};

199 二叉树的右视图

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

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> que;
        if(root!=nullptr)
            que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            while(size)
            {
                TreeNode*node = que.front();
                que.pop();
                if(size == 1) //每次往result插入时，插入每次循环的最后一个即可
                    result.push_back(node->val);
                if(node->left)
                    que.push(node->left);
                if(node->right)
                    que.push(node->right);
                size--;
            }
        }
        return result;
    }
};

637 二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> result;
        queue<TreeNode*> que;
        if(root!=nullptr)
            que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            double sum = 0; //用sum记录总和，最后除以size即可
            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);
            }
            result.push_back(sum/size);
        }
        return result;
    }
};

429 N叉树的层序遍历

?给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
       vector<vector<int>> result;
        queue<Node*> que;
        if(root != nullptr)
            que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            vector<int> vec;
            while(size--)
            {
                Node*node = que.front();
                que.pop();
                vec.push_back(node->val);
                for(int i = 0; i < node->children.size(); i++) //只有这里有区别
                {
                    if(node->children[i])
                        que.push(node->children[i]);
                }
            }
            result.push_back(vec);
        }
        return result; 
    }
};

515 在每一层里找最大值

您需要在二叉树的每一行中找到最大的值。

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> que;
        if(root!=nullptr)
            que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            int MaxValue = INT_MIN;
            while(size--)
            {
                TreeNode*node = que.front();
                que.pop();
                MaxValue = MaxValue > (node->val) ? MaxValue:(node->val); //这里判断一下
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(MaxValue);
        }
        return result;
    }
};

116填充每个节点的下一个右侧结点的指针

给定一个?完美二叉树?，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为?NULL。

初始状态下，所有?next 指针都被设置为?NULL。

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if(root != NULL)
            que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            while(size)
            {
                Node*node = que.front();
                que.pop();
                if(size == 1) //处理最右面节点
                {
                    node->next = NULL;
                }
                else
                {
                    node->next = que.front(); //处理其他节点
                }
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
                size--;
            }
        }
        return root;
    }
};

104 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        int depth = 0;
        if(root != nullptr)
            que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            depth++;
            while(size--)
            {
                TreeNode*node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return depth;
    }
};

111 二叉树的最小深度

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            depth++; // 记录最小深度
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (!node->left && !node->right) { // 当左右孩子都为空的时候，说明是最低点的一层了，退出
                    return depth;
                }
            }
        }
        return depth;
    }
};