0.找某一节点的双亲节点
TreeNode*daan=NULL;
void tracking(TreeNode*cur,TreeNode*p)
{
if(cur==NULL)return;
if(cur->left==p||cur->right==p)
{
daan=cur;
}
tracking(cur->left,p);
tracking(cur->right,p);
}
1.前中后序遍历(递归写法)
给你二叉树的根节点 root ，返回它节点值的 前中后序 遍历。
代码
/**
* 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:
//前序
void tracking(TreeNode*cur,vector<int> &vec)
{
if(cur==NULL)return;
vec.push_back(cur->val);
tracking(cur->left,vec);
tracking(cur->right,vec);
}
//中序
void tracking(TreeNode*cur,vector<int> &vec)
{
if(cur==NULL)return;
tracking(cur->left,vec);
vec.push_back(cur->val);
tracking(cur->right,vec);
}
//后序
void tracking(TreeNode*cur,vector<int> &vec)
{
if(cur==NULL)return;
tracking(cur->left,vec);
tracking(cur->right,vec);
vec.push_back(cur->val);
}
//主函数
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
tracking(root,res);
return res;
}
};
2.前中后序遍历(迭代写法)
给你二叉树的根节点 root ，返回它节点值的 前中后序 遍历。
前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
为什么要先加入右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
代码
//前序
//前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> cur;
vector<int> daan;
if(root==NULL)return daan;
cur.push(root);
while(!cur.empty())
{
TreeNode*dan = cur.top();
cur.pop();
daan.push_back(dan->val);
if(dan->right!=NULL)
{
cur.push(dan->right);
}
if(dan->left!=NULL)
{
cur.push(dan->left);
}
}
return daan;
}
//前序
vector<int> preorderTraversal(TreeNode* root) {
vector<int> daan;
stack<TreeNode*> cur;
if(root==NULL)return daan;
TreeNode*p=root;
while(p!=NULL||!cur.empty())
{
if(p)
{
daan.push_back(p->val);
cur.push(p);
p=p->left;
}
else
{
p=cur.top();
cur.pop();
p=p->right;
}
}
return daan;
}
//中序
1.沿着根的左孩子,依次入栈,直到左孩子为空,说明已经找到可以输出的节点
2.栈顶元素出栈并访问,若其右孩子为空,则继续进行2操作,若右孩子不空则进行1操作
<!--那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。-->
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur != NULL || !st.empty()) {
if (cur != NULL) { // 指针来访问节点，访问到最底层
st.push(cur); // 将访问的节点放进栈
cur = cur->left; // 左
} else {
cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
st.pop();
result.push_back(cur->val); // 中
cur = cur->right; // 右
}
}
return result;
}
//后序
//与前序第一种类似,改下顺序即可,前序是先处理中间节点输入答案数组中,后将右,左节点压入栈中,最后得到的结果是中///左右的答案.
//后序则先将处理中间节点，将左节点,右节点压入栈中,得到结果为中右左的答案数组,最后翻转答案数组即为左右中
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> cur;
vector<int> daan;
if(root==NULL)return daan;
cur.push(root);
while(!cur.empty())
{
TreeNode*dan=cur.top();
cur.pop();
daan.push_back(dan->val);
if(dan->left)
{
cur.push(dan->left);
}
if(dan->right)
{
cur.push(dan->right);
}
}
reverse(daan.begin(),daan.end());
return daan;
}
3.层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
代码
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
};
3.层序遍历II
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
代码
反转即可
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> result;
if(root==NULL)return result;
stack<vector<int>> st;
queue<TreeNode*> que;
que.push(root);
while(!que.empty())
{
int n = que.size();
vector<int> rec;
for(int i=0;i<n;i++)
{
TreeNode*dan=que.front();
que.pop();
rec.push_back(dan->val);
if(dan->left)que.push(dan->left);
if(dan->right)que.push(dan->right);
}
st.push(rec);
}
// reverse(result.begin(),result.end());
while(!st.empty())
{
result.push_back(st.top());
st.pop();
}
return result;
}
};
4.n叉树的前序(后序)遍历
代码
//前序
class Solution {
public:
vector<int> res;
vector<int> preorder(Node* root) {
dfs(root);
return res;
}
void dfs(Node*root)
{
if(root==NULL)return;
res.push_back(root->val);
for(auto c:root->children)
{
dfs(c);
}
}
};
//后序
class Solution {
public:
vector<int> res;
vector<int> postorder(Node* root) {
dfs(root);
return res;
}
void dfs(Node*root)
{
if(root==NULL)return;
for(auto c:root->children)
{
dfs(c);
}
res.push_back(root->val);
}
};
5.先序遍历二叉树中第K个节点（k保证有效）
代码
class Solution {
public:
TreeNode*cur;
void dfs(TreeNode*root,int &key)
{
if(root==NULL)
{
return;
}
if(!(--key))
{
cur=root;
return;
}
dfs(root->left,key);
dfs(root->right,key);
}
TreeNode* deleteNode(TreeNode* root, int key) {
dfs(root,key);
return cur;
}
};
