仅做记录

树的前序、中序、后序、层次遍历(递归/非递归)

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

class Solution:
    def initTree(self):    # 构造树
        m = TreeNode(0)
        m1 = TreeNode(1)
        m2 = TreeNode(2)
        m.left = m1
        m.right = m2
        m3 = TreeNode(3)
        m4 = TreeNode(4)
        m1.left = m3
        m1.right = m4
        m5 = TreeNode(5)
        m6 = TreeNode(6)
        m2.left = m5
        m2.right = m6
        m7 = TreeNode(7)
        m8 = TreeNode(8)
        m3.left = m7
        m3.right = m8
        m9 = TreeNode(9)
        m4.left = m9
        return m

    def layer(self, root):    # 层次遍历
        if not root:
            return None
        queue = [root]
        while queue:
            t = queue.pop(0)
            print(t.val, end=" ")
            if t.left:
                queue.append(t.left)
            if t.right:
                queue.append(t.right)

    def preOrder(self, root):    # 先序遍历-递归
        if not root:
            return None
        print(root.val, end=" ")
        self.preOrder(root.left)
        self.preOrder(root.right)

    def preOederNo(self, root):    # 先序遍历-非递归
        if not root:
            return None
        # out = []
        stack = []
        while root or stack:
            while root:
                # out.append(root.val)
                print(root.val, end=" ")
                stack.append(root)
                root = root.left
            if stack:
                t = stack.pop()
                root = t.right
        # return out

    def midOrder(self, root):    # 中序遍历-递归
        if not root:
            return None
        self.midOrder(root.left)
        print(root.val, end=" ")
        self.midOrder(root.right)

    def midOederNo(self, root):    # 中序遍历-非递归
        if not root:
            return None
        # out = []
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            if stack:
                t = stack.pop()
                # out.append(root.val)
                print(t.val, end=" ")
                root = t.right
        # return out

    def postOrder(self, root):    # 后序遍历-递归
        if not root:
            return None
        self.postOrder(root.left)
        self.postOrder(root.right)
        print(root.val, end=" ")

    def postOederNo(self, root):    # 后序遍历-非递归
        if not root:
            return None
        out = []
        stack = []
        while root or stack:
            while root:
                out.append(root.val)
                stack.append(root)
                root = root.right
            if stack:
                t = stack.pop()
                root = t.left
        for i in out[::-1]:
            print(i, end=" ")

if __name__ == '__main__':
    t = Solution()
    # 构造树
    m = t.initTree()
    print("层次遍历：", end=" ")
    t.layer(m)
    print("")
    print("先序遍历(递归)：", end=" ")
    t.preOrder(m)
    print("")
    print("先序遍历(非递归)：", end=" ")
    t.preOederNo(m)
    print("")
    print("中序遍历(递归)：", end=" ")
    t.midOrder(m)
    print("")
    print("中序遍历(非递归)：", end=" ")
    t.midOederNo(m)
    print("")
    print("后序遍历(递归)：", end=" ")
    t.postOrder(m)
    print("")
    print("后序遍历(非递归)：", end=" ")
    t.postOederNo(m)

运行结果