这篇文章有两个点,第一个是题目本身,第二个是我觉得很不错的用栈来模拟递归。
做过这么多树的题目后应该觉得用递归很简单吧,我们只需要交换每一个节点的左右节点就行了。
要注意这里要交换指针才能达到效果,交换数是不行的。
然后简单的递归就实现了:
void MirrorReverseTree(treeNode* tree)
{
if (!tree)
return;
//swap left&right
treeNode* tmp = tree->left;
tree->left = tree->right;
tree->right = tmp;
if (tree->left)
MirrorReverseTree(tree->left);
if (tree->right)
MirrorReverseTree(tree->right);
}
用循环来实现
有人说所有的递归都可以用循环来实现。。但是可以肯定的是,使用递归的时候编写代码要简单一些。
但是使用递归的话,要小心,避免stackoverflow。
这个题呢,我们要遍历每个节点,然后做和递归同样的事情,可以用while循环判断是否到达了叶子节点,可是我仍然觉得直接这样写挺难的,我再想想。。
然而有另一种很巧妙的思路:
由于递归的本质是编译器生成了一个函数调用的栈,因此用循环来完成同样任务时最简单的办法就是用一个辅助栈来模拟递归。首先我们把树的头结点放入栈中。在循环中,只要栈不为空,弹出栈的栈顶结点,交换它的左右子树。 如果它有左子树, 把它的左子树压入栈中; 如果它有右子树, 把它的右子树压入栈中。这样在下次循环中就能交换它儿子结点的左右子树了。
这种认识是很重要的。
所以我们利用这种想法来实现,我们每经过一个节点就把这个节点压入栈,然后对每个节点做同样的事情就可以了。
其实这种题就是说,怎么简单的遍历到整个树。
code:
//non recursive way:
//using a stack
void mirrorReverseTree_2(treeNode* tree)
{
if (!tree)
return;
std::stack<treeNode*> nodeStack;
nodeStack.push(tree);
while (nodeStack.size())
{
//swap left&right
treeNode* tmp = tree->left;
tree->left = tree->right;
tree->right = tmp;
if (tree->left)
nodeStack.push(tree->left);
if (tree->right)
nodeStack.push(tree->right);
}
}
其实这个函数里,
if (tree->left) nodeStack.push(tree->left); if (tree->right) nodeStack.push(tree->right);
这两个语句让人深深的感觉到有递归的影子啊!
文章参考何海涛大神文章