二叉树的层序遍历及其变形

文章目录

• 二叉树的层序遍历
• • 变形

二叉树的层序遍历

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

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]

层序遍历
使用队列，队头出队带入他的左右节点

vector<vector<int>> levelOrder(TreeNode* root) {
   
        vector<vector<int>> ret;//用来记录的是每一层的元素
        queue<TreeNode*> s;//用来入队，出队带入左右节点
        int levelsize=0;
        if(root)//如果根不为空，就入队，进行后续的操作
        {
   
            s.push(root);
            levelsize=1;
        }
        
        while(!s.empty())//当队列为空，就结束了
        {
   
            levelsize=s.size();
            vector<int> v;
            while(levelsize--)//队列一层的元素
            {
   
                TreeNode* parm=s.front();//记录队头
                v.push_back(parm->val);//先入队
                if(parm->left)//左不为空，带入
                {
   
                s.push(parm->left);
                
                }
                if(parm->right)
                {
   
                s.push(parm->right);
                
                }
                s.pop();//出队
            }
            ret.push_back(v);//插入一层的元素
            
        }
        return ret;
    }

变形

1. 计算第k层的节点个数

size=ret[k-1];

2. 计算一共的节点个数

for(auto e:ret)
{
   
	total+=e.size();//将每一个的元素个数相加
}

3. 计算深度

hight=ret.size();//ret的个数

4. 二叉树自底向上遍历

reverse(ret.begin(),ret.end());//翻转一下即可