1) . 前序遍历 : 根节点 -- 左节点 -- 右节点
2) . 中序遍历 : 左节点 -- 跟节点 -- 右节点
3) . 后序遍历 : 左节点 -- 右节点 -- 根节点
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode() : val(0), left(nullptr), right(nullptr) {} 8 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 9 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} 10 * }; 11 */ 12 class Solution { 13 public: 14 vector<int> ans; 15 // map<int, int> vis; 16 void dfs(TreeNode* cur) { 17 if(!cur) return; 18 TreeNode* lson = cur->left; 19 TreeNode* rson = cur->right; 20 ans.push_back(cur->val); //前序 21 if(lson == nullptr && rson == nullptr) { 22 ans.push_back(cur->val); 23 return; 24 } 25 if(lson != nullptr) { 26 dfs(lson); 27 } 28 //ans.push_back(cur->val); 中序 29 if(rson != nullptr) { 30 dfs(rson); 31 } 32 //ans.push_back(cur->val); 后序 33 } 34 35 vector<int> preorderTraversal(TreeNode* root) { 36 TreeNode* head = root; 37 dfs(head); 38 return ans; 39 } 40 };
//层序
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> tt = vector<vector<int>> (10000);
int dep = 0;
struct Node {
TreeNode* node;
int depth;
};
queue<Node> q;
void bfs(TreeNode* cur) {
if(!cur) return;
q.push({cur, 0});
while(!q.empty()) {
Node now = q.front(); q.pop();
tt[now.depth].push_back(now.node->val);
TreeNode* lson = now.node->left, *rson = now.node->right;
if(lson != nullptr) {
q.push({lson, now.depth + 1});
}
if(rson != nullptr) {
q.push({rson, now.depth + 1});
}
}
for(int i = 0; i < 10000; i++) {
if(tt[i].size()) {
ans.push_back(tt[i]);
}
else break;
}
}
vector<vector<int>> levelOrder(TreeNode* root) {
bfs(root);
return ans;
}
};