首页 > 代码库 > 二叉树的遍历
二叉树的遍历
二叉树的4种遍历方法，包括前序遍历，中序遍历，后序遍历，层次遍历的递归和非递归遍历。
前序遍历：
//递归vector<int> preorderTraversal(TreeNode* root) { vector<int>array; traversal(root,array); return array;}void traversal(TreeNode *root,vector<int>&array){ if(root==NULL) return ; array.push_back(root->val); traversal(root->left,array); traversal(root->right,array);}//非递归vector<int>preorderTraversal(TreeNode *root){ vector<int> result; if(root==NULL) return result; stack<TreeNode *>tree; TreeNode *p=root; while(p||!tree.empty()){ while(p){ result.push_back(p->val); tree.push(p); p=p->left; } if(!tree.empty()){ p=tree.top(); tree.pop(); p=p->right; } } return result;}
中序遍历：
//递归vector<int> inorderTraversal(TreeNode* root) { vector<int> array; traversal(root,array); return array;}void traversal(TreeNode *root,vector<int> & array){ if(root==NULL) return ; traversal(root->left,array); array.push_back(root->val); traversal(root->right,array);}//非递归vector<int> inorderTraversal(TreeNode* root) { vector <int> result; if(root==NULL) return result; stack<TreeNode *>tree; TreeNode *p=root; while(p||!tree.empty()){ while(p){ tree.push(p); p=p->left; } p=tree.top(); result.push_back(p->val); tree.pop(); p=p->right; } return result;}
中序遍历：
//递归vector<int>postorderTraversal(TreeNode* root) { vector<int>array; traversal(root,array); return array;}void traversal(TreeNode *root,vector<int>&array){ if(root==NULL) return; traversal(root->left,array); traversal(root->right,array); array.push_back(root->val);}//非递归vector<int>postorderTraversal(TreeNode* root) { vector<int>result; if(root==NULL) return result; stack<bool>visited; stack<TreeNode *>tree; TreeNode *p; bool visitr; p=root; while(p||!tree.empty()){ while(p){ tree.push(p); visited.push(false); p=p->left; } p=tree.top(); visitr=visited.top(); if(!p->right||visitr){ // 如果节点的右子树为空或者右子树已经访问过，那么就可以访问该节点 result.push_back(p->val); tree.pop(); visited.pop(); p=NULL; } else{ //右子树不为空并且没有访问过，则将节点标识为访问过右节点 visited.pop(); visited.push(true); p=p->right; } } return result;}
层次遍历：
//递归vector<vector<int>>levelOrder(TreeNode* root) { vector<vector<int>>result; for(int level=0; ;level++){ vector<int>levelResult; if(!order(root,levelResult,level)) break; result.push_back(levelResult); }return result;}int order(TreeNode *root,vector<int>&array,int level){ if(root==NULL||level<0) return 0; if(level==0){ array.push_back(root->val); return 1; } return order(root->left,array,level-1) + order(root->right,array,level-1);}//非递归vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;vector<int> raw;if(root==NULL) return result;TreeNode * last=root;queue<TreeNode *> Queue;Queue.push(root);while(!Queue.empty()){ TreeNode * temp=Queue.front(); Queue.pop(); raw.push_back(temp->val); if(temp->left) Queue.push(temp->left); if(temp->right) Queue.push(temp->right); if(temp==last){ result.push_back(raw); raw.clear(); last=Queue.back(); }}return result;}
二叉树的遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。