菜鸟笔记
提升您的技术认知

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

阅读 : 24
  • 前序遍历: 节点-左子树-右子树(中-左-右)
  • 中序遍历: 左子树-节点-右子树(左-中-右)
  • 后续遍历: 左子树-右子树-节点(左-右-中)

数据结构


//  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());
}
  • 参考文献
    彻底吃透二叉树的前中后序递归法和迭代法!!