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

电玩女神 2022-05-12 03:38 159阅读 0赞

# 前言 #

python中二叉树的定义：

class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None

[如何使用python建立一个二叉树][python]

# 前序 #

class Solution:
        def preorderTraversal(self, root):
            """ :type root: TreeNode :rtype: List[int] """
            ret = []
            stack = [root]
            while stack:
                node = stack.pop()
                if node:
                    ret.append(node.val)
                    stack.append(node.right)
                    stack.append(node.left)
            return ret

通过使用栈先保存要访问的结点，这里有一点需要注意的是，我们每次先将node的右结点加入到了stack中，然后再加入的是左结点，这样我们就可以保证在每次stack弹栈的时候，左结点始终先弹出来了。

# 中序 #

class Solution:
        def inorderTraversal(self, root):
            """ :type root: TreeNode :rtype: List[int] """
            res, stack = [], []
            while True:
    
                while root:
                    stack.append(root)
                    root = root.left
                if not stack:
                    return res
                node = stack.pop()
                res.append(node.val)
                root = node.right

通过stack每次都保存左子树的所有结点，当左子树已经全部加入了，这时候要访问左子树的叶子结点，然后需要**转向**，加入当前结点的右结点，然后再继续上述的过程。

# 后序 #

class Solution:
        def postorderTraversal(self, root):
            """ :type root: TreeNode :rtype: List[int] """
            nodes = []
            # to_visit是存储结点的栈
            to_visit = []
            cur = root
            last_node = None
            # 如果当前结点或者要遍历的结点不为空就持续遍历
            while cur or len(to_visit) != 0:
                # 一直访问左子树，直至为空
                if cur:
                    to_visit.append(cur)
                    cur = cur.left
                else:
                    # 取到栈中最顶部的结点，然后判断是否有右结点并且右结点是否已经访问过
                    top_node = to_visit[-1]
                    if top_node.right and last_node != top_node.right:
                        cur = top_node.right
                    else:
                        # 访问结点，并且将last_node记录为当前访问的结点
                        nodes.append(top_node.val)
                        last_node = top_node
                        to_visit.pop()
            return nodes

[python]: https://blog.csdn.net/sty945/article/details/81912015