Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说
完全二叉树的层序遍历_n个结点的二叉树有几种形态,希望能够帮助你!!!。

tree traversal (树的遍历) - 层序遍历 (level order traversal) - 二叉树的层序遍历

1. tree traversal (树的遍历)

1.1 深度优先搜索 (depth-first search，DFS)

我们采用深度作为优先级，从根节点开始一直到达某个确定的叶子节点，然后再返回根节点到达另一个分支。深度优先搜索策略可以根据根节点、左孩子树和右孩子树的相对顺序被细分为前序遍历、中序遍历和后序遍历。

前序遍历 (preorder traversal) - 中序遍历 (inorder traversal) - 后序遍历 (postorder traversal)

1.2 广度优先搜索 - 宽度优先搜索 - 横向优先搜索 (breadth-first search，BFS)

我们按照高度顺序一层一层的访问整棵树，高层次的节点将会比低层次的节点先被访问到。

下图中的节点依照不同的策略遍历，访问的顺序均为 1, 2, 3, 4, 5。宽度优先搜索划分层次为 [[1], [2, 3], [4, 5]]。

递归实现的效率一般比对应的非递归实现低。如果在函数中使用了两个递归调用，效率低下的问题就会变得更为严重。

2. 二叉树的层序遍历

给你一个二叉树，返回其按层序遍历得到的节点值。(即逐层地，从左到右访问所有节点)。

2.1 示例

二叉树：[3,9,20,null,null,15,7]

 3 / \ 9 20 / \ 15 7 

返回其层次遍历结果：

[ [3], [9,20], [15,7] ] 

2.2 Source Code

//============================================================================ // Name : level_order // Author : Yongqiang Cheng // Version : Version 1.0.0 // Copyright : Copyright (c) 2019 Yongqiang Cheng // Description : Hello World in C++, Ansi-style //============================================================================ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ret_data = { }; queue<TreeNode *> queue_data = { }; TreeNode *proot = root; TreeNode *front_data = NULL; if (NULL == root) { return {}; } queue_data.push(proot); while (!queue_data.empty()) { vector<int> tmp = { }; int queue_size = queue_data.size(); for (int idx = 0; idx < queue_size; idx++) { front_data = queue_data.front(); queue_data.pop(); tmp.push_back(front_data->val); if (NULL != front_data->left) { queue_data.push(front_data->left); } if (NULL != front_data->right) { queue_data.push(front_data->right); } } ret_data.push_back(tmp); } return ret_data; } }; 

2.3 递归实现

递归实现较为简单，首先确认树非空，然后调用递归函数 helper(node, level)，参数是当前节点和节点的层次。程序过程如下：

• 输出列表称为 levels，当前最高层数就是列表的长度 len(levels)。比较访问节点所在的层次 level 和当前最高层次 len(levels) 的大小，如果前者更大就向 levels 添加一个空列表。
• 将当前节点插入到对应层的列表 levels[level] 中。
• 递归非空的孩子节点：helper(node.left / node.right, level + 1)。

复杂度分析

• 时间复杂度：O(N)，每个节点恰好会被运算一次。
• 空间复杂度：O(N)，保存输出结果的数组包含 N 个节点的值。

今天的分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。