二叉树的遍历

二叉树节点的定义

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) 		{}
};

前序遍历

递归实现

vector<int> preOrderTraversal(TreeNode* root) {
		vector<int> res;
		preOrder(root,res);
		return res;
}
    
void preOrder(TreeNode* root, vector<int> &res){
		if (root == nullptr){
				return;
		}
		res.push_back(root->val);
		preOrder(root->left,res);
		preOrder(root->right,res);
}

非递归实现

当栈不为空时，栈顶元素出栈，如果其右子节点不为空，则右子节点入栈，其左字节点不为空，则左字节点入栈，这样出栈时，则会先出左子节点，再出右子节点，则能够完成树的前序遍历

vector<int> preOrderTraversal(TreeNode* root) {
		vector<int> res;
		if (root == nullptr){
				return res;
		}
		stack<TreeNode*> s;
		s.push(root);
		while (!s.empty()){
				TreeNode* temp = s.top();
				s.pop();
				res.push_back(temp->val);
				if (temp->right){
						s.push(temp->right);
				}
				if (temp->left){
						s.push(temp->left);
				}
		}
		return res;
}

中序遍历

递归实现

vector<int> inOrderTraversal(TreeNode* root) {
		vector<int> res;
		inOrder(root,res);
		return res;
}

void inOrder(TreeNode* root, vector<int> &res){
		if (root == nullptr){
				return;
		}
		inOrder(root->left,res);
		res.push_back(root->val);
		inOrder(root->right,res);
}

非递归实现

vector<int> inorderTraversal(TreeNode* root) {
		vector<int> res;
		if (root == nullptr){
				return res;
		}
		stack<TreeNode*> stk;
		while (!stk.empty() || root != nullptr){
				//不断往左子树方向走，每走一次就将当前节点保存到栈中
				while (root != nullptr){
						stk.push(root);
						root = root->left;
				}
				//当前节点为空，说明左边走到头了，从栈中弹出节点并保存
				//然后转向右边节点，继续上面整个过程
				root = stk.top();
				stk.pop();
				res.push_back(root->val);
				root = root->right;
		}
		return res;
}

后序遍历

递归实现

vector<int> postOrderTraversal(TreeNode* root) {
		vector<int> res;
		postOrder(root,res);
		return res;
}

void postOrder(TreeNode* root, vector<int> &res){
		if (root == nullptr){
				return;
		}
		postOrder(root->left,res);
		postOrder(root->right,res);
		res.push_back(root->val);
}

非递归实现

因为后序遍历二叉树的顺序是先访问左子树，再访问右子树，最后访问根节点。当用堆栈来存储节点，必须分清返回根节点时，是从左子树返回的，还从右子树返回的。所以，使用辅助指针prev指向最近访问过的节点，来判断是否从右子树返回。也可以在节点中增加一个标志域，记录是否已被访问。

vector<int> postorderTraversal(TreeNode* root) {
		vector<int> res;
		if (root == nullptr){
				return res;
		}
		stack<TreeNode*> stk;
		TreeNode* prev = nullptr;
		while (root != nullptr || !stk.empty()){
				while (root != nullptr){//不断往左子树方向走
						stk.push(root);
						root = root->left;
				}
				root = stk.top();
				stk.pop();
				if (root->right && root->right != prev){//右子树存在且未被访问
						stk.push(root);//从左子树返回，不能弹出根节点，应再压回栈内
						root = root->right;
				}else{
						res.push_back(root->val);
						prev = root;
						root = nullptr;
				}
		}
		return res;
}

按层次遍历

//遍历结果将一个层次存储到一个vector中
vector<vector<int>> levelOrder(TreeNode* root) {
		vector<vector<int>> result;
		//树为空直接返回
		if (root == nullptr){
				return result;
		}
		queue<TreeNode*> q;
		q.push(root); //先将根节点入队
		while (!q.empty()){
				vector<int> temp;
				int n = q.size();
				for (int i = 0; i < n; i++){
						TreeNode* node = q.front();
						q.pop(); //出队并保存节点
						temp.push_back(node->val);
						//将节点的左子树入队
						if (node->left != nullptr){
								q.push(node->left);
						}
            //将节点的右子树入队
						if (node->right != nullptr){
								q.push(node->right);
						}
				}
				result.push_back(temp);
		}
		return result;
}