二叉树层序遍历

我这个小垃圾，按照模板做，感觉真不错   举一反三，天天都有着感觉就好，随缘刷题，哪天想起就哪天刷，真的太容易忘记了。

leetcode 102  二叉树的层序遍历

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        queueque;
        if(root!=nullptr)
        que.push(root);
        vector>result;
        while(!que.empty())
        {
            int size=que.size();
            vectorvec;
            for(int i=0;ival);
                if(node->left)
                que.push(node->left);
                if(node->right)
                que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

leetcode 107 二叉树的层序遍历2

class Solution {
public:
    vector> levelOrderBottom(TreeNode* root) {
        queueque;
        if(root!=nullptr)
        que.push(root);
        vector>result;//结果数组
        while(!que.empty())
        {
            vectorvec;
            int size=que.size();//因为que的size是不断变化的
            for(int i=0;ival);
                //然后查找头节点的左右孩子，依次入队列
                if(node->left)
                que.push(node->left);
                if(node->right)
                que.push(node->right);
            }
            //将存储值的数组存入结果数组
            result.push_back(vec);
        }
        //题目要求自底向上,我们可以用reverse把result翻转
        reverse(result.begin(),result.end());
        return result;
    }
};

leetcode 199 二叉树的右视图

class Solution {
public:
    vector rightSideView(TreeNode* root) {
        //使用层序遍历，右侧的元素就是最后一个元素，所以我们只需要再基础的层序遍历上判断，这是否是这一层的最后一个元素，将他放入结果数组
        queueque;
        if(root!=nullptr)
        que.push(root);
        //定义结果数组
        vectorresult;
        while(!que.empty())
        {
            int size=que.size();
            for(int i=0;ival);
                //将左右孩子入队列
                if(node->left)
                que.push(node->left);
                if(node->right)
                que.push(node->right);
            }
        }
        return result;
    }

leetcode 637 二叉树的层平均值

class Solution {
public:
    vector averageOfLevels(TreeNode* root) {
        queueque;
        if(root!=nullptr)
        que.push(root);
        vectorresult;
        while(!que.empty())
        {
            double sum=0;
            int size=que.size();
            for(int i=0;ival;
                if(node->left)
                que.push(node->left);
                if(node->right)
                que.push(node->right);
            }
            //将平均值传入result数组
            result.push_back(sum/size);
        }
        return result;
    }
};

leetcode 429 n叉树的层序遍历

class Solution {
public:
    vector> levelOrder(Node* root) {
        //n叉树，说明可以不止2个孩子，可以多个孩子,我们只要增加一个for循环即可
        queueque;
        //判断头节点是否存在
        if(root!=nullptr)
        que.push(root);
        //结果数组,返回层数据
        vector>result;
        while(!que.empty())
        {
            int size=que.size();
            vectorvec;
            for(int i=0;ival);
                //因为n叉树，所以右n个孩子，所以我们不能用二叉树的模板来做了
                for(int i=0;ichildren.size();++i)
                {
                    //将每个孩子入队列
                    if(node->children[i])
                    que.push(node->children[i]);
                }
            }
            result.push_back(vec);
        }
        return result;
    }

leetcode 515 在每个树行中找最大值
 

class Solution {
public:
    vector largestValues(TreeNode* root) {
        //树行  层序遍历，比较左右孩子的大小，入数组
        queueque;
        if(root!=nullptr)
        que.push(root);
        //定义结果数组
        vectorresult;
        while(!que.empty())
        {
            int size=que.size();
            int maxvalue=INT_MIN;//取每一层最大值
            for(int i=0;ival>maxvalue?node->val:maxvalue;
                if(node->left)
                que.push(node->left);
                if(node->right)
                que.push(node->right);
            }
            result.push_back(maxvalue);
        }
        return result;
    }
};

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

class Solution {
public:
    Node* connect(Node* root) {
        queueque;
        if(root!=NULL)
        que.push(root);
        while(!que.empty())
        {
            int size=que.size();
            Node* nodepro=NULL;
            Node* node=NULL;
            //声明结果数组
            vectorresult;
            for(int i=0;inext=node;//本层前一个结点next指向本结点
                    nodepro=nodepro->next;
                }
                if(node->left)
                que.push(node->left);
                if(node->right)
                que.push(node->right);
            }
            nodepro->next=NULL;
        }
        return root;
    }
};

leetcode117         填充每个节点的下一个右侧点指针2  代码没有变

class Solution {
public:
    Node* connect(Node* root) {
        queueque;
        if(root!=NULL)
        que.push(root);
        while(!que.empty())
        {
            Node*nodepro=NULL;
            Node*node=NULL;
            int size=que.size();
            for(int i=0;inext=node;
                    nodepro=node;
                }
                if(node->left)
                que.push(node->left);
                if(node->right)
                que.push(node->right);
            }
            nodepro->next=NULL;
        }
        return root;
    }
};

leetcode 104 二叉树的最大深度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queueque;
        if(root!=nullptr)
        que.push(root);
        //定义一个变量记录深度
        int deepth=0;
        while(!que.empty())
        {
            int size=que.size();
            deepth++;
            for(int i=0;ileft)
                que.push(node->left);
                if(node->right)
                que.push(node->right);
            }
        }
        return deepth;
    }
};

leetcode111 二叉树的最小深度

class Solution {
public:
    int minDepth(TreeNode* root) {
        queueque;
        if(root!=nullptr)
        que.push(root);
        //定义一个变量记录深度
        int deepth=0;
        while(!que.empty())
        {
            int size=que.size();
            deepth++;
            for(int i=0;ileft)
                que.push(node->left);
                if(node->right)
                que.push(node->right);
                if(!node->left&&!node->right)//计算最小深度，找到没有左右孩子的，直接break
                return deepth;
            }
        }
        return deepth;
    }
};