二叉树遍历

递归

void per(TreeNode* root,vector<int>& res)//前序 { if(root==nullptr) return; res.emplace_back(root->val); per(root->left,res); per(root->right,res); } void mid(TreeNode* root,vector<int>& res)//中序 { if(root==nullptr) return; mid(root->left,res); res.emplace_back(root->val); mid(root->right,res); } void beh(TreeNode* root,vector<int>& res)//后序 { if(root==nullptr) return; beh(root->left,res); beh(root->right,res); res.emplace_back(root->val); } vector<int> traversal(TreeNode* root) { vector<int> res; // per(root,res); // mid(root,res); // beh(root,res); return res; }

非递归

vector<int> per(TreeNode* root)//前序 { stack<TreeNode*> stk; vector<int> res; if(root==nullptr) return res; stk.emplace(root); while(!stk.empty()) { TreeNode* prev=stk.top(); stk.pop(); res.emplace_back(prev->val); if(prev->right!=nullptr) stk.emplace(prev->right); if(prev->left!=nullptr) stk.emplace(prev->left); } return res; } vector<int> mid(TreeNode* root)//中序 { stack<TreeNode*> stk; vector<int> res; if(root==nullptr) return res; while(root||!stk.empty()) { while(root!=nullptr) { stk.emplace(root); root=root->left; } root=stk.top(); stk.pop(); res.emplace_back(root->val); root=root->right; } return res; } vector<int> beh(TreeNode* root)//后序 { stack<TreeNode*> stk; vector<int> res; if(root==nullptr) return res; stk.emplace(root); while(!stk.empty()) { TreeNode* prev=stk.top(); stk.pop(); res.emplace_back(prev->val); if(prev->left!=nullptr) stk.emplace(prev->left); if(prev->right!=nullptr) stk.emplace(prev->right); } reverse(res.begin(),res.end()); return res; }

层次遍历

vector<vector<int>> level(TreeNode* root) { queue<TreeNode*> q; vector<vector<int>> res; if(root==nullptr) return res; q.emplace(root); while(!q.empty()) { int len=q.size(); vector<int> tmp; for(int i=0;i<len;i++) { TreeNode* prev=q.front(); q.pop(); tmp.emplace_back(prev->val); if(prev->left!=nullptr) q.emplace(prev->left); if(prev->right!=nullptr) q.emplace(prev->right); } res.emplace_back(tmp); } return res; }