二叉树遍历-递归迭代整理

• 前序遍历： 节点-左子树-右子树（中-左-右）
• 中序遍历： 左子树-节点-右子树（左-中-右）
• 后续遍历： 左子树-右子树-节点（左-右-中）

数据结构

//  Definition for a binary tree node.
  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) {
  }
 };

递归版本

前序遍历

void preOrder(TreeNode * root){
  
	cout<<root->val; // process node 
	preOrder(root->left);
	preOrder(root->right);
	
}

中序遍历

void inOrder(TreeNode * root){
  
	
	inOrder(root->left);
	cout<<root->val; // process node 
	inOrder(root->right);
	
}

后序遍历

void postOrder(TreeNode * root){
  
	
	postOrder(root->left);
	postOrder(root->right);
	cout<<root->val; // process node 
	
}

迭代版本

前序遍历

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

中序遍历

vector<int> inorderTraversal(TreeNode * root){
  
	vector<int> res;
	if(root == NULL) return res;
	stack<TreeNode *>s;
	TreeNode * cur = root;
	while(!cur||!s.empty()){
  
		if(cur != NULL){
  
			s.push(cur);
			cur = cur->left;
		}else{
  
			cur = s.top();
			s.pop();
			res.push_back(cur->val);
			cur = cur->right;
		}
	}
	return res;

}

后序遍历：
前序（中左右）- 调整（中右左）-翻转（左右中）-得到后续遍历

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

	}
	res.reverse(res.begin(), res.end());
}

• 参考文献
  彻底吃透二叉树的前中后序递归法和迭代法！！