二叉树的递归与非递归遍历

• 前序遍历二叉树
• 递归遍历
• 非递归遍历
• 中序遍历二叉树
• 递归遍历
• 非递归遍历
• 后序遍历二叉树
• 递归遍历
• 非递归遍历

将二叉树遍历的结果保存到vector中返回。
递归遍历代码简短，也相对容易理解，此不赘述。咱们重点来看一下非递归遍历。

前序遍历二叉树

递归遍历

void preORecursive(TreeNode* pRoot, vector<int>& vec)
{
	if(pRoot == NULL) return;
	vec.push_back(pRoot->val);
	preORecursive(pRoot->left, vec);
	preORecursive(pRoot->right, vec);
}
vector<int> preOrderRecursive(TreeNode* pRoot)
{
	vector<int> vec;
	if(pRoot == NULL) return vec;
	preORecursive(pRoot, vec);
	return vec;
}

非递归遍历

• 思想： 栈后法，右左子孩子入栈法

///栈后法，右左子孩子入栈法


vector<int> preOrder(TreeNode* pRoot)
{
	vector<int> vec;
	stack<TreeNode*> sta;
	if(pRoot)
	{
		vec.push_back(pRoot->val);
		sta.push(pRoot->right);
		sta.push(pRoot->left);
	}
	while(!sta.empty())
	{
		auto node = sta.top();
		vec.push_back(node->val);
		sta.pop();
		if(node->right) sta.push(node->right);
		if(node->right) sta.push(node->left);
	}
	return vec;
}

中序遍历二叉树

递归遍历

void inORecursive(TreeNode* pRoot, vector<int>& vec)
{
	if(pRoot == NULL) return;
	
	inORecursive(pRoot->left, vec);
	vec.push_back(pRoot->val);
	inORecursive(pRoot->right, vec);
}
vector<int> inOrderRecursive(TreeNode* pRoot)
{
	vector<int> vec;
	if(pRoot == NULL) return vec;
	inORecursive(pRoot, vec);
	return vec;
}

非递归遍历

• 思想： 栈后法，右臂入栈法

话不多说，直接上代码：

// 栈后法，右臂入栈法

vector<int> inOrder(TreeNode* pRoot)
{
	vector<int> vec;
	stack<TreeNode*> sta;
	while(pRoot)
	{
		sta.push(pRoot->left);
		pRoot = pRoot->left;
	}

	while(!sta.empty())
	{
		auto node = sta.top();
		vec.push_back(node->val);
		sta.pop();
		node = node->right;
		while(node)
		{
			sta.push(node);
			node = node->left;
		}
	}
	return vec;
}

后序遍历二叉树

递归遍历

void postORecursive(TreeNode* pRoot, vector<int>& vec)
{
	if(pRoot == NULL) return;
	
	postORecursive(pRoot->left, vec);
	postORecursive(pRoot->right, vec);
	vec.push_back(pRoot->val);
}
vector<int> postOrderRecursive(TreeNode* pRoot)
{
	vector<int> vec;
	if(pRoot == NULL) return vec;
	postORecursive(pRoot, vec);
	return vec;
}

非递归遍历

/**
 * 对于一个节点而言，要实现访问顺序为左儿子-右儿子-根节点，可以利用后进先出的栈，在节点不为空的前提下，
 * 依次将根节点，右儿子，左儿子压栈。故我们需要按照根节点-右儿子-左儿子的顺序遍历树，
 * 而我们已经知道先序遍历的顺序是根节点-左儿子-右儿子，故只需将先序遍历的左右调换并把访问方式打印改为压入另一个栈即可。
 * 最后一起打印栈中的元素。
 */
 vector<int> postOrderTraversal(TreeNode* pRoot)
 {
 	vector<int> vec;
 	stack<TreeNode*> sta1;
 	stack<TreeNode*> sta2;
 	TreeNode* q;

 	if(!pRoot) sta1.push(pRoot);
 	while(!sta1.empty())
 	{
 		q = sta1.top();
 		sta2.push(q);
 		sta1.pop();
 		if(q->left != NULL) sta1.push(q->left);
 		if(q->right != NULL) sta1.push(q->right);
 	}
 	while(!sta2.empty())
 	{
 		vec.push_back(sta2.top()->val);
 		sta2.pop();
 	}
 	return vec;
 }