0%

二叉树的前中后序遍历的非递归实现(Python)

发表于 更新于 分类于 ，
本文字数： 2.7k 阅读时长 ≈ 2 分钟

二叉树的前中后序遍历的非递归实现

二叉树定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class TreeNode:
    def __init__(self, x, L=None, R=None):
        self.val = x
        self.left = L
        self.right = R

def List2TN(lst, needs=None):
    '''
    lst: a leetcode way tree list
    needs: A list of Int. The nodes whose indexes provided in this list would be returned.
    '''
    nit = []
    root = TreeNode(lst[0])
    tnQ = [root]
    i = 1
    if needs and i in needs:
        nit.append(root)
    while i < len(lst):
        cur = tnQ.pop(0)
        if lst[i] != None:
            cur.left = TreeNode(lst[i])
            tnQ.append(cur.left)
            if needs and i in needs:
                nit.append(cur.left)
        i += 1
        if i >= len(lst):
            break
        if lst[i] != None:
            cur.right = TreeNode(lst[i])
            tnQ.append(cur.right)
            if needs and i in needs:
                nit.append(cur.right)
        i += 1
    if needs:
        return root, nit
    else:
        return root

前序遍历

具体过程

1、首先申请一个新的栈，记为stack。
2、然后将头节点head压入stack中。
3、每次从stack中弹出栈顶节点，记为cur，然后打印cur节点的值。如果cur右孩子不为空的话，将cur的右孩子先压入stack中。最后如果cur的左孩子不为空的话，将cur的左孩子压入stack中。
4、不断重复步骤3，直到stack为空，全部过程结束。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def preorderTraversal(self,root):
        """
        根->左->右
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = [root]
        res = []
        while stack:
            cur = stack.pop()
            res.append(cur.val)
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)
        return res

中序遍历

具体过程

  • 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def inorderTraversal(self, root):
        """
        左->根->右
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = []
        cur = root
        res = []
        while stack or cur:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                node = stack.pop()
                res.append(node.val)
                cur = node.right
        return res

后序遍历

具体过程

方法一：使用两个栈实现

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
17
class 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def bfs(root):
    queue = []
    # 根节点加入队列中
    queue.append(root)
    res = []
    while queue:
        temp = queue.pop(0)
        l = temp.left
        r = temp.right
        if l:
            queue.append(l)
        if r:
            queue.append(r)
        res.append(temp.val)
    return res