[LeetCode]226. Invert Binary Tree 颠倒二叉树

题目描述:

Invert a binary tree.

to

题目大意:

自己领悟题目描述。


 

既然是要颠倒,那么肯定是从下到上。而三种遍历方式之中,后序遍历是从左节点 -> 右节点 -> 根节点的顺序遍历的。所以直接用后序遍历走一遍,在到根节点的时候进行交换就行了。噢记得如果根节点为空,就什么都不要做直接返回。

我的代码:

理所应当的Accept了。不过我还是再查查别人的做法。


 

答案地址:http://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73034

前辈是用前序遍历做的。仔细一想也是OK。因为不论如何都只是左节点与右节点的交换。而第二种递归的方法,竟然有:

 

这种情况出现。其实有些诧异。但仔细一想,这个函数的返回值如果就是传进来的root,那么这段代码中的赋值也没有什么问题。

什么?中序遍历?也行。后来我发现其实只要遍历所有节点其实就行了。

之后是迭代法:(我一直觉得能递归就一定能迭代,因为有栈和队列辅助。)

在这里我又看到了上次所看到的。先用 node 取 q.front() ,然后再用 q.pop() 把这个 q.front() 扔出去。那么这个节点就做完了。

之后执行 swap(node -> left , node -> right) 函数,将两个节点交换。

最后再把 node -> left 和 node -> right 塞进队列里,如果空的话就不必了。

这样的话,就能保证每一有元素的层都能被遍历到,一层一层走下来。好像是那个叫 BFS 的广度优先算法。

妙!