1上陕、叉樹的層次遍歷
/**
* 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>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> q;
if(root) q.push(root);
while(q.size())
{
vector<int> level;
int len = q.size();
for(int i = 0;i < len;i ++) {
TreeNode* t = q.front();
q.pop();
level.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
res.push_back(level);
}
return res;
}
};
2桩砰、前序遍歷
遞歸
/**
* 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<int> res;
void dfs(TreeNode* root) {
if(root) {
res.push_back(root->val);
dfs(root->left);
dfs(root->right);
}
}
vector<int> preorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
};
迭代
/**
* 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<int> preorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode* p = root;
stack<TreeNode*> stk;
while(p || stk.size())
{
while(p) {
res.push_back(p->val);
stk.push(p);
p = p->left;
}
p = stk.top()->right;
stk.pop();
}
return res;
}
};
3、中序遍歷
遞歸
/**
* 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<int> res;
void dfs(TreeNode* root)
{
if(root) {
dfs(root->left);
res.push_back(root->val);
dfs(root->right);
}
}
vector<int> inorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
};
迭代
/**
* 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<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
TreeNode* p = root;
while(p || stk.size())
{
while(p) {
stk.push(p);
p = p->left;
}
p = stk.top();
stk.pop();
res.push_back(p->val);
p = p->right;
}
return res;
}
};
4释簿、后續(xù)遍歷
遞歸
/**
* 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<int> res;
void dfs(TreeNode* root)
{
if(root)
{
dfs(root->left);
dfs(root->right);
res.push_back(root->val);
}
}
vector<int> postorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
};
迭代
后續(xù)遍歷的做法如下：
1亚隅、前序遍歷的順序：根，左庶溶，右
2煮纵、可以根據(jù)類型前序遍歷的思想，遍歷出：根偏螺，右行疏，左
3、再通過 2 中遍歷出來的順序套像，通過反轉(zhuǎn)得到后序遍歷：左酿联，右，根
/**
* 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<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode* > stk;
TreeNode* p = root;
while(p || stk.size())
{
while(p) {
res.push_back(p->val);
stk.push(p);
p = p->right;
}
p = stk.top()->left;
stk.pop();
}
reverse(res.begin(), res.end());
return res;
}
};
5夺巩、前序遍歷 + 中序遍歷構(gòu)建二叉樹
/**
* 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:
unordered_map<int, int> pos;
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir)
{
if(pl > pr || il > ir) return NULL;
TreeNode* root = new TreeNode(preorder[pl]);
int k = pos[preorder[pl]];
int len = k - il;
root->left = build(preorder, inorder, pl + 1, pl + len, il, k - 1);
root->right = build(preorder, inorder, pl + len + 1, pr, k + 1, ir);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for(int i = 0 ;i < preorder.size();i ++) pos[inorder[i]] = i;
return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
}
};
6贞让、中序遍歷 + 后序遍歷構(gòu)建二叉樹
/**
* 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:
unordered_map<int, int> pos;
TreeNode* build(vector<int> postorder, vector<int>& inorder, int pl, int pr, int il, int ir)
{
if(pl > pr || il > ir) return NULL;
TreeNode* root = new TreeNode(postorder[pr]);
int k = pos[postorder[pr]];
int len = k - il;//len為前序的長(zhǎng)度
root->left = build(postorder, inorder, pl, pl + len - 1, il, k - 1);
root->right = build(postorder, inorder, pl + len, pr - 1, k + 1, ir);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
for(int i = 0;i < inorder.size();i ++) pos[inorder[i]] = i;
return build(postorder, inorder, 0, postorder.size() - 1, 0, inorder.size() - 1);
}
};
