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

川长思鸟来 2022-12-30 15:50 84阅读 0赞

> 二叉树的前序、中序、后序遍历需要用到数据结构栈。

下面给出一种统一写法：

> 下面是中序遍历的写法：

class Solution2:
        def midOrder(self, root):
            stack = [root]
            res = []
            while stack:
                s = stack.pop()
                if type(s) is Node:
                    if s.right:
                        stack.append(s.right)
                    stack.append(s.val)
                    if s.left:
                        stack.append(s.left)
                else:
                    res.append(s)
            return res

如果改成前序遍历：（只需要将入栈的顺序改一下就可以了）

def midOrder(self, root):
        stack = [root]
        res = []
        while stack:
            s = stack.pop()
            if type(s) is Node:
                if s.right:
                    stack.append(s.right)
                if s.left:
                    stack.append(s.left)
                stack.append(s.val)
            else:
                res.append(s)
        return res

下面是后续：

def midOrder(self, root):
        stack = [root]
        res = []
        while stack:
            s = stack.pop()
            if type(s) is Node:
                stack.append(s.val)
                if s.right:
                    stack.append(s.right)
                if s.left:
                    stack.append(s.left)
            else:
                res.append(s)
        return res