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

[toc]

二叉树定义

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为空,全部过程结束。

代码实现

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为空时,整个过程结束。

代码实现

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为空,过程停止。

代码实现

方法一:

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

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

未经允许不得转载:晨飞小窝 » 二叉树的前中后序遍历的非递归实现(Python)

赞 (0)