二叉树遍历问题-LeetCode 144、94、145、102、987（前序，中序，后序，层次，垂序）
二叉树遍历问题-LeetCode 144、94、145、102、987（前序，中序，后序，层次，垂序）
作者：TeddyZhang，公众号：算法工程师之路
1
编程题
【LeetCode #144】二叉树的前序遍历
给定一个二叉树，返回它的 前序 遍历。
/**
* 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<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> sta;
vector<int> res;
if(root == nullptr) return res;
sta.push(root);
while(!sta.empty()){
TreeNode* tmp = sta.top();
sta.pop();
if(tmp->right != nullptr) sta.push(tmp->right);
if(tmp->left != nullptr) sta.push(tmp->left);
res.push_back(tmp->val);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
【LeetCode #94】二叉树的中序遍历
给定一个二叉树，返回它的 中序 遍历。
/**
* 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<int> inorderTraversal(TreeNode* root) {
vector<int> res;
if(root == nullptr) return res;
stack<TreeNode*> sta;
TreeNode* cur = root;
while(cur != nullptr || !sta.empty()){
if(cur != nullptr){
sta.push(cur);
cur = cur->left;
}else{
cur = sta.top();
sta.pop();
res.push_back(cur->val);
cur = cur->right;
}
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
【LeetCode #145】二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。
/**
* 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<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if(root == nullptr) return res;
stack<TreeNode*> sta;
sta.push(root);
while(!sta.empty()){
TreeNode* tmp = sta.top();
sta.pop();
if(tmp->left != nullptr) sta.push(tmp->left);
if(tmp->right != nullptr) sta.push(tmp->right);
res.insert(res.begin(), tmp->val);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
【LeetCode #102】二叉树层次遍历
给定一个二叉树，返回它的 层次 遍历。
/**
* 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>> res;
if(root == nullptr) return res;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
int size = que.size();
vector<int> level;
while(size--){
TreeNode* tmp = que.front();
que.pop();
level.push_back(tmp->val);
if(tmp->left != nullptr) que.push(tmp->left);
if(tmp->right != nullptr) que.push(tmp->right);
}
res.push_back(level);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
【LeetCode #987】二叉树垂序遍历
给定二叉树，按垂序遍历返回其结点值。
对位于 (X, Y) 的每个结点而言，其左右子结点分别位于 (X-1, Y-1) 和 (X+1, Y-1)。 把一条垂线从 X = -infinity 移动到 X = +infinity ，每当该垂线与结点接触时，我们按从上到下的顺序报告结点的值（ Y 坐标递减）。 如果两个结点位置相同，则首先报告的结点值较小。 按 X 坐标顺序返回非空报告的列表。每个报告都有一个结点值列表。
输入：[3,9,20,null,null,15,7] 输出：[[9],[3,15],[20],[7]] 解释： 在不丧失其普遍性的情况下，我们可以假设根结点位于 (0, 0)： 然后，值为 9 的结点出现在 (-1, -1)； 值为 3 和 15 的两个结点分别出现在 (0, 0) 和 (0, -2)； 值为 20 的结点出现在 (1, -1)； 值为 7 的结点出现在 (2, -2)。
解题思路：
通过对每个节点赋予（x, y）的位置标记，从而垂序遍历就是x保持不变，对y轴的值进行遍历，因此我们使用map<x, vector<pair>>的数据结构，使用map来对x遍历，而每个x都对应一个数组，数组中保存在节点的横坐标为x的一系列节点！由于题目中要求为有序的，因此我们需要对vector<pair>进行排序，然后存入结果中！,>,="">
注意：既然是哈希，能不能使用unordered_map呢？大家可以试试，应该是不行的，因为题目中要求打印时从左向右，因此需要使用有序的map结构，而不是无序的unordered_map结构！
/**
* 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:
map<int, vector<pair<int, int>>> tree;
void dfs(TreeNode* root, int x, int y){
if(root == nullptr) return;
tree[x].push_back(make_pair(y, root->val));
dfs(root->left, x-1, y+);
dfs(root->right, x+, y+);
}
vector<vector<int>> verticalTraversal(TreeNode* root) {
vector<vector<int>> res;
if(root == nullptr) return res;
dfs(root, , );
for(auto& node: tree){ // 由于要修改node的值，需要加引用
sort(node.second.begin(), node.second.end());
vector<int> tmp;
for(auto t: node.second){
tmp.push_back(t.second); // 获取val
}
res.push_back(tmp);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree