金溪网站建设制作,最好的营销策划公司,做网站教程百度云,网站模板下载 免费树森林二叉树先序遍历先序遍历先序遍历后序遍历中序遍历中序遍历
1.前序遍历
leetcode题目链接
1.1 递归 前序遍历递归方式 class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint res;if(root){res.push_back(root-val);ve…树森林二叉树先序遍历先序遍历先序遍历后序遍历中序遍历中序遍历
1.前序遍历
leetcode题目链接
1.1 递归 前序遍历递归方式 class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint res;if(root){res.push_back(root-val);vectorint l preorderTraversal(root-left);res.insert(res.end(),l.begin(),l.end());vectorint r preorderTraversal(root-right);res.insert(res.end(),r.begin(),r.end());}return res;}
};1.2 非递归 前序遍历迭代方式一 class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint res;stackTreeNode* s;while( root || !s.empty()){if(root){res.push_back(root-val);s.push(root);root root-left;}else{root s.top() , s.pop();root root-right;}}return res;}
};前序遍历迭代方式二 class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint res;stackTreeNode* s;while( root || s.size()){while(root){res.push_back(root-val);s.push(root);root root-left;}root s.top() , s.pop();root root-right;}return res;}
};2 中序遍历
leetcode题目链接
2.1 递归 中序遍历递归方式 class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint res;if(root){vectorint l inorderTraversal(root-left);res.insert(res.end(),l.begin(),l.end());res.push_back(root-val);vectorint r inorderTraversal(root-right);res.insert(res.end(),r.begin(),r.end());}return res;}
};非递归 中序遍历迭代方式一 class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint res;stackTreeNode* s;while(root || s.size()){if( root ){s.push(root);root root-left;}else{root s.top() , s.pop();res.push_back(root-val);root root-right;}}return res;}
};中序遍历迭代方式二 class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint res;stackTreeNode* s;while(root || !s.empty()){while(root){s.push(root);root root-left;}root s.top() , s.pop();res.push_back(root-val);root root-right;}return res;}
};3 后序遍历
leetcode题目链接
3.1 递归 后序递归遍历方式 class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint res;if(root){vectorint l postorderTraversal(root-left);res.insert(res.end(),l.begin(),l.end());vectorint r postorderTraversal(root-right);res.insert(res.end(),r.begin(),r.end());res.push_back(root-val);}return res;}
};3.2 非递归 后序遍历迭代方式 class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint res;stackTreeNode* s;TreeNode* pre NULL;while(root || s.size()){if(root){s.push(root);root root-left;}else{root s.top();if(root-right pre ! root-right)root root-right;else{s.pop();res.push_back(root-val);pre root;root NULL;}}}return res;}
};
