二叉树前中后层序遍历的Python实现

田田田

image.png

• 前序遍历

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


class Solution(object):
    def pre_order(self, root):
        res = []
        if root:
            res.append(root.val)
            res += self.pre_order(root.left)
            res += self.pre_order(root.right)
        return res


def main():
    list1 = [1, None, 2, 3]
    root = TreeNode(list1[0])
    p1 = TreeNode(list1[1])
    p2 = TreeNode(list1[2])
    p3 = TreeNode(list1[3])
    root.left = p1
    root.right = p2
    p2.left = p3
    p = Solution()
    pre_order_list = p.pre_order(root)
    print pre_order_list


if __name__ == '__main__':
    main()

• 中序遍历

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


class Solution(object):
    def in_order(self, root):
        res = []
        if root:
            res += self.in_order(root.left)
            res.append(root.val)
            res += self.in_order(root.right)
        return res


def main():
    list1 = [1, None, 2, 3]
    root = TreeNode(list1[0])
    p1 = TreeNode(list1[1])
    p2 = TreeNode(list1[2])
    p3 = TreeNode(list1[3])
    root.left = p1
    root.right = p2
    p2.left = p3
    p = Solution()
    in_order_list = p.in_order(root)
    print in_order_list


if __name__ == '__main__':
    main()

• 后续遍历

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


class Solution(object):
    def post_order(self, root):
        res = []
        if root:
            res += self.post_order(root.left)
            res += self.post_order(root.right)
            res.append(root.val)
        return res


def main():
    list1 = [1, None, 2, 3]
    root = TreeNode(list1[0])
    p1 = TreeNode(list1[1])
    p2 = TreeNode(list1[2])
    p3 = TreeNode(list1[3])
    root.left = p1
    root.right = p2
    p2.left = p3
    p = Solution()
    post_order_list = p.post_order(root)
    print post_order_list


if __name__ == '__main__':
    main()

• 层序遍历

image.png

• 代码1：

#!/usr/bin/python
# -*- coding: UTF-8 -*-
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def Sequence_order(self, root):
        res = []
        if root:
            if root.left:
                res.append(root.left.val)
            if root.right:
                res.append(root.right.val)
            res += self.Sequence_order(root.left)
            res += self.Sequence_order(root.right)
        return res


def main():
    list1 = [1, 2, 3, 4, 5, 6, 7]
    root = TreeNode(list1[0])
    p1 = TreeNode(list1[1])
    p2 = TreeNode(list1[2])
    p3 = TreeNode(list1[3])
    p4 = TreeNode(list1[4])
    p5 = TreeNode(list1[5])
    p6 = TreeNode(list1[6])
    root.left = p1
    root.right = p2
    p1.left = p3
    p1.right = p4
    p2.left = p5
    p2.right = p6
    p = Solution()
    Sequence_order_list = p.Sequence_order(root)

    res = []
    res.append(root.val)    #根节点单独拿出来了

    for i in Sequence_order_list:
        res.append(i)
    print res


if __name__ == '__main__':
    main()

• 代码2：

from Queue import Queue


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


class Solution(object):
    def sequence_order(self, root):
        res = []
        q = Queue(maxsize=0)

        if root == None:
            return None

        q.put(root)
        res.append(root.val)

        while not q.empty():
            first = q.get()
            if first.left:
                q.put(first.left)
                res.append(first.left.val)

            if first.right:
                q.put(first.right)
                res.append(first.right.val)

        return res


def main():
    list1 = [1, 2, 3, 4, 5, 6, 7]
    root = TreeNode(list1[0])
    p1 = TreeNode(list1[1])
    p2 = TreeNode(list1[2])
    p3 = TreeNode(list1[3])
    p4 = TreeNode(list1[4])
    p5 = TreeNode(list1[5])
    p6 = TreeNode(list1[6])
    root.left = p1
    root.right = p2
    p1.left = p3
    p1.right = p4
    p2.left = p5
    p2.right = p6

    p = Solution()
    sequence_order_list = p.sequence_order(root)
    print sequence_order_list


if __name__ == '__main__':
    main()