二叉树遍历
二叉树的前序、中序、后序遍历,可以用递归或迭代两种方法实现。
递归法
//中序遍历 class Solution{ public: vector<int> vec; vector<int> InOrderRecursive(BT* root, vector<int> vec) { if(root==nullptr) return vec; vec = InOrder(root->left, vec); vec.push_back(root->val); vec = InOrder(root->right, vec); return vec; }
迭代法
通过堆栈和智能指针来实现二叉树的迭代遍历
BT.h头文件如下
#ifndef BINARYTREE_H #define BINARYTREE_H struct BinaryTree{ int val; BinaryTree* left; BinaryTree* right; BinaryTree(x): val(x), left(nullptr), right(nullptr) {} } typedef BinaryTree BT; #endif
函数主体如下:
中序遍历
class Solution{ public: vector<int> InOrderTraversal(BT* root){ vector<int> vec; if(root==nullptr) return vec; stack<BT*> st; shared_ptr<BT> p1 = make_shared<BT> (BT(val)); while(p1!=nullptr || !st.empty()) { while(p1!=nullptr) { st.push(p1); p1 = p1->left; } p1 = st.top(); st.pop(); vec.push_back(p1->val); p1 = p1->right; } return vec; }
前序遍历
vector<int> PreOrderTraversal(BT* root){ vector<int> vec; if(root==nullptr) return vec; stack<BT*> st; shared_ptr<BT> p1 = make_shared<BT> (BT(val)); while(p1!=nullptr || !st.empty()) { while(p1!=nullptr) { //前序遍历先将节点值输入进vec中,然后向左把节点压入st中 vec.push_back(p1->val); st.push(p1); p1 = p1->left; } p1 = st.top(); st.pop(); p1 = p1->right; } return vec; }
后序遍历
vector<int> PostOrderTraversal(BT* root){ vector<int> vec; if(root==nullptr) return vec; stack<BT*> st; shared_ptr<BT> p1 = make_shared<BT> (BT(val)); TreeNode *preVis = root; //后续遍历需要考虑到先右节点再根节点 while(p1!=nullptr || !st.empty()) { //把左子树叶节点放进去 while(p1!=nullptr) { st.push(p1); p1 = p1->left; } p1 = st.top(); //如果无右子树或右子树已经被访问过,再访问根节点 if(p1->right==nullptr || p1->right==preVis) { vec.push_back(p1->val); st.pop(); pre = p1; p1 = nullptr; } else p1 = p1->right; } return vec; } };
层序遍历
//运用队列来实现 vector<int> levelTraversal(BT* root) { vector<int> vec; if(root==nullptr) return vec; queue<BT*> q; q.push(root); while(!q.empty()) { TreeNode* temp; for(int i=0;i<q.size();++i){ temp = q.front(); vec.push_back(temp->val); if(temp->left!=nullptr) q.push(temp->left); if(temp->right!=nullptr) q.push(temp->right); q.pop(); } } return vec; }