LeetCode 题69~71： 二叉树的层级遍历

本文主要是介绍LeetCode 题69~71： 二叉树的层级遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目描述

给定一课二叉树（如下），分别完成从上往下层级遍历、从下往上层级遍历、Z字形从上往下层级遍历：
4
/ \
2 6
/ \ / \
1 3 5 7
输出结果如下：
第一种情况：从上往下层级遍历：
[
[4],
[2，6],
[1，3，5，7]
]
第二种情况：从下往上层级遍历：
[
[1，3，5，7],
[2，6],
[4]
]
第三种情况：Z字形从上往下层级遍历：
[
[4],
[6，2],
[1，3，5，7]
]

2. 二叉树的数据结构：

struct TreeNode
{int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int v = 0, TreeNode *l = NULL, TreeNode *r = NULL):val(v),left(l),right(r){}
};

3. 从上往下层级遍历

3.1 思路分析

《剑指offer》中有个题目和这个很类似，其只是层次遍历二叉树，没有要求把每层的节点单独放在一起的。其做法是：每次打印一个节点的时候，如果该结点有子结点，则把该结点的子结点放到一个队列的尾部；接下来到队列的头部取出最早进入队列的结点；重复前面的打印操作，直到队列中所有的结点都被打印出来为止。
但是本题稍微复杂一点的是，我们要把各个层的数分开，存到一个二维向量里面，但大体思路还是基本相同的。首先，建立一个队列，然后先把根节点放进去，接着找根节点的左右两个子节点，然后去掉根节点，此时队列里的元素就是下一层的所有节点，用一个for循环遍历它们，然后存到一个一维向量里，遍历完之后再把这个一维向量存到二维向量里，以此类推，可以完成层序遍历。

3.2 方法1：迭代法

vector<vector<int>> levelOrder(TreeNode *root){vector<vector<int>> result;if(root == NULL){return result;}queue<TreeNode *> q;q.push(root);while(!q.empty()){vector<int> oneLevel;int size = q.size();for(int i = 0; i < size; i++){TreeNode *node = q.front();q.pop();oneLevel.push_back(node->val);if(node->left != NULL){q.push(node->left);}if(node->right != NULL){q.push(node->right);}}result.push_back(oneLevel);}return result;
}

3.3 方法2：递归法

递归的核心在于：需要一个二维数组，和一个变量level，当level递归到上一层的个数时，我们新建一个空层，继续往里面加数字。

vector<vector<int>> levelOrder(TreeNode *root)
{vector<vector<int>> result;traverse(root, 0, result);return result;
}
void traverse(TreeNode *root, size_t level, vector<vector<int>> &result){if(root == NULL){return;}if(result.size() == level){result.push_back(vector<int>());}result[level].push_back(root->val);if(root->left != NULL){traverse(root->left, level+1, result);}if(root->right != NULL){traverse(root->right, level+1, result);}
}

4. 从下往上层级遍历

4.1 思路分析

这种情况与上面的情况一致，区别在于最后的输出顺序不一样

4.2 方法1：迭代法

vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int> > result;if(root == NULL){return result;}queue<TreeNode *> q;q.push(root);while(!q.empty()){vector<int> oneLevel;int size = q.size();for(int i = 0; i < size; i++){TreeNode *node = q.front();q.pop();oneLevel.push_back(node->val);if(node->left != NULL){q.push(node->left);}if(node->right != NULL){q.push(node->right);}}result.insert(result.begin(), oneLevel);}return result;}

4.3 方法2：递归法

vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int> > result;levelorder(root, 0, result);return vector<vector<int> > (result.rbegin(), result.rend());}void levelorder(TreeNode *root, int level, vector<vector<int> > &result){if (root == NULL){return;}if (result.size() == level){result.push_back({});}result[level].push_back(root->val);if (root->left) {levelorder(root->left, level + 1, result);}if (root->right) {levelorder(root->right, level + 1, result);}
}

5. Z字形从上往下层级遍历

5.1 思路分析

这道题是之前的层级遍历的变形，不同之处在于一行是从左到右遍历，下一行是从右往左遍历，交叉往返的之字形的层序遍历。根据其特点我们用到栈的后进先出的特点，这道题我们维护两个栈，相邻两行分别存到两个栈中，进栈的顺序也不相同，一个栈是先进左子结点然后右子节点，另一个栈是先进右子节点然后左子结点，这样出栈的顺序就是我们想要的之字形了。

5.2 方法1：迭代法（双栈实现）

vector<vector<int>> zigzagLevelOrder(TreeNode *root) {vector<vector<int>> result;if(root == NULL){return result;}stack<TreeNode *> s1;stack<TreeNode *> s2;s1.push(root);vector<int> out; //存放每一行的输出while(!s1.empty() || !s2.empty()){while(!s1.empty()){TreeNode *pCur = s1.top();s1.pop();out.push_back(pCur->val);if(pCur->left != NULL){s2.push(pCur->left);}if(pCur->right != NULL){s2.push(pCur->right);}}if(!out.empty()){result.push_back(out);}out.clear();while(!s2.empty()){TreeNode *pCur = s2.top();s2.pop();out.push_back(pCur->val);if(pCur->right != NULL){s1.push(pCur->right);}if(pCur->left){s1.push(pCur->left);}}if(!out.empty()){result.push_back(out);}out.clear();}return result;
}

5.3 方法2：迭代法（队列实现）

vector<vector<int>> zigzagLevelOrder2(TreeNode *root) //队列实现Z字型层级遍历{vector<vector<int>> result;if(root == NULL){return result;}queue<TreeNode *> q;bool left_to_right = true; //记录是从左到右还是从右到左，每一层结束就翻转一下vector<int> out; //记录每一层的数据q.push(root);q.push(nullptr);while(!q.empty()){TreeNode *pCur = q.front();q.pop();if(pCur != NULL){out.push_back(pCur->val);if(pCur->left != NULL)q.push(pCur->left);if(pCur->right != NULL)q.push(pCur->right);}else{if(left_to_right){result.push_back(out);}else{reverse(out.begin(), out.end());result.push_back(out);}out.clear();left_to_right = !left_to_right ;if(q.size() > 0)q.push(nullptr);}}return result;
}

5.4 方法3：递归法（队列实现）

    vector<vector<int> > zigzagLevelOrder3(TreeNode *root)  vector<vector<int>> result;recursive (root, 1, result, true); return result;}void recursive(TreeNode *root, size_t level, vector<vector<int>> &result, bool left_to_right){if (!root) return;if (level > result.size())result.push_back(vector<int>());if (left_to_right)result[level-1].push_back(root->val);elseresult[level-1].insert(result[level-1].begin(), root->val);recursive (root->left, level+1, result, !left_to_right);recursive (root->right, level+1, result, !left_to_right);
}

ps: 完整测试代码见我的代码片：https://code.csdn.net/snippets/1762076

参考文章：
1、http://www.cnblogs.com/grandyang/p/4051321.html
2、http://www.cnblogs.com/grandyang/p/4051326.html
3、http://www.cnblogs.com/grandyang/p/4297009.html
4、Acm之家： Binary Tree Zigzag Level Order Traversal

Note: 以上几篇文章对我写作本文起了很大作用，在此非常感谢。

这篇关于LeetCode 题69~71： 二叉树的层级遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---