非递归实现交换二叉树的左右子节点_二叉树左右节点交换非递归

思路一：

         两个队列

思路二：

         栈

struct TreeNode
{
	int m_nValue;
	TreeNode *m_pLeft;
	TreeNode *m_pRight;
};
 
void ExchangeNode(TreeNode *pRoot)
{
	stack<TreeNode *> s;
	if (pRoot)
		s.push(pRoot);
	while (!s.empty())
	{
		TreeNode *cur = s.top();
		s.pop();
		TreeNode *pTmp = cur->m_pLeft;
		cur->m_pLeft = cur->m_pRight;
		cur->m_pRight = pTmp;
		if (cur->m_pLeft)
			s.push(cur->m_pLeft);
		if (cur->m_pRight)
			s.push(cur->m_pRight)
	}
}

非递归前序、中序、后序遍历

两个栈

void PreOrderNonRecursive(TreeNode * node) 
{
	stack<TreeNode *> s;
	s.push(node);
	while(!s.empty()) 
	{
		TreeNode * n = s.pop();
		visit(n);
		if(n->right!=NULL) s.push(n->right);
		if(n->left!=NULL) s.push(n->left);
	}
}
 
void InOrderNonRecursive(TreeNode * node) 
{
	stack<Tree