二叉树的前中后序遍历的非递归实现
二叉树定义
1 | class TreeNode: |
前序遍历
具体过程
1、首先申请一个新的栈,记为stack。
2、然后将头节点head压入stack中。
3、每次从stack中弹出栈顶节点,记为cur,然后打印cur节点的值。如果cur右孩子不为空的话,将cur的右孩子先压入stack中。最后如果cur的左孩子不为空的话,将cur的左孩子压入stack中。
4、不断重复步骤3,直到stack为空,全部过程结束。
代码实现
1 | class Solution(object): |
中序遍历
具体过程
- 1、申请一个新的栈,记为
stack
,申请一个变量cur
,初始时令stack
为空,cur
等于头节点。 - 2、先把
cur
节点压入栈中,对以cur节点为头的整棵子树来说,依次把整棵树的左边界压入栈中,即不断令cur=cur.left
,然后重复步骤2。 - 3、不断重复步骤2,直到发现
cur
为空,此时从stack
中弹出一个节点,记为node
。打印node
的值,并让cur=node.right
,然后继续重复步骤2。 - 4、当
stack
为空并且cur
为空时,整个过程结束。
代码实现
1 | class Solution(object): |
后序遍历
具体过程
方法一:使用两个栈实现
1、申请一个栈,记为s1,然后将头节点压入s1中。
2、从s1中弹出的节点记为cur,然后先把cur的左孩子压入s1中,然后把cur的右孩子压入s1中。
3、在整个过程中,每一个从s1中弹出的节点都放进第二个栈s2中。
4、不断重复步骤2和步骤3,直到s1为空,过程停止。
5、从s2中依次弹出节点并打印,打印的顺序就是后序遍历的顺序了。
方法二:使用一个栈实现
1、申请一个栈,记为stack,将头节点压入stack,同时设置两个变量h和c。在整个流程中,h代表最近一次弹出并打印的节点,c代表当前stack的栈顶节点,初始时令h为头节点,c为null。
2、每次令c等于当前stack的栈顶节点,但是不从stack中弹出节点,此时分以下三种情况。
(1)如果c的左孩子不为空,并且h不等于c的左孩子,也不等于c的右孩子,则把c的左孩子压入stack中。
(2)如果情况1不成立,并且c的右孩子不为空,并且h不等于c的右孩子,则把c的右孩子压入stack中。
(3)如果情况1和情况2都不成立,那么从stack中弹出c并打印,然后令h等于c。
3、一直重复步骤2,直到stack为空,过程停止。
代码实现
方法一:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution(object):
def postorderTraversal(self, root):
"""
左->右->根
:type root: TreeNode
:rtype: List[int]
"""
stack1 = [root]
stack2 = []
while stack1:
cur = stack1.pop()
stack2.append(cur.val)
if cur.left:
stack1.append(cur.left)
if cur.right:
stack1.append(cur.right)
return stack2[::-1]
层次遍历
bfs
1 | def bfs(root): |