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

二叉树遍历-ag真人游戏

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

数据结构


//  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<val; // process node 
	preorder(root->left);
	preorder(root->right);
	
}

中序遍历

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

后序遍历

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

迭代版本

前序遍历

vector preordertraversal(treenode * root){
  
	vector res;
	if(root == null) return res;
	stacks;
	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 inordertraversal(treenode * root){
  
	vector res;
	if(root == null) return res;
	stacks;
	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 postordertraversal(treenode* root){
  
	vector res;
	if(root == null) return res;
	stack 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());
}
  • 参考文献
    彻底吃透二叉树的前中后序递归法和迭代法!!
网站地图