算法学习【二叉树篇】(2)

对应leetcode题目

• 102.二叉树的层序遍历
• 107.二叉树的层次遍历II
• 199.二叉树的右视图
• 637.二叉树的层平均值
• 429.N叉树的层序遍历
• 515.在每个树行中找最大值
• 116.填充每个节点的下一个右侧节点指针
• 117.填充每个节点的下一个右侧节点指针II
• 104.二叉树的最大深度
• 111.二叉树的最小深度

二叉树的层次遍历

这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

class Solution{
public:
  vector> levelOrder(TreeNode* root) {
    queue que;
    vector> result;
    if(root!=NULL) que.push(root);
    while(!que.empty()){
      int size = que.size();
      vector vec;
      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;
  }
};

如果是从底向上遍历，则添加一行

reverse(result.begin(),result.end());