python | #实现二叉树先序，中序和后序遍历#

NC45 实现二叉树先序，中序和后序遍历

日期：2021.9.4

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

#
# 
# @param root TreeNode类 the root of binary tree
# @return int整型二维数组
#
class Solution:
    def threeOrders(self , root ):
        # write code here
        if root is None:
            return [None,None,None]
        def first(root):
            '''
            前序遍历，先读中节点，然后读左子树，最后右子树
            '''
            stack = [] #存储扫过的节点
            res = [] #存储值
            while root or stack:
                while root is not None: #一直读到当前子树的最底层的最左侧
                    stack.append(root)
                    res.append(root.val)#添加父节点的值
                    root = root.left # 走向左子树
                if stack:
                    node = stack.pop() #读取最后加入的节点
                    if node.right is not None:
                        root = node.right #走向右子树
            return res
        def middle(root):
            '''
            中序遍历，先读左子树，然后读父节点，最后右子树
            '''
            stack = []
            res = []
            while root or stack:
                while root is not None:
                    stack.append(root)
                    root = root.left # 一直走到左子树的尽头
                if stack:
                    node = stack.pop()
                    res.append(node.val) #读取最后一个加入节点的值（左子树为none的父节点的值）
                    if node.right is not None:
                        root = node.right #走向右子树
            return res
        def last(root):
            '''
            后序遍历，先读左子树，然后读右子树，最后父节点
            【父节点的值、右节点、左节点】
            【父节点的值、右节点、左节点的值、左—右节点、左-左节点】
            【父节点的值、右节点、左节点的值、左—右节点、左-左节点的值】
            实现后序遍历
            '''
            stack = []
            res = []
            stack.append(root) #压入父节点
            while stack:
                node = stack.pop()
                if type(node) is TreeNode: #如果当前节点是父节点，将当前节点替换成节点值，并压入右节点、左节点
                    stack.append(node.val)
                    if node.right:
                        stack.append(node.right)
                    if node.left:
                        stack.append(node.left)
                else:
                    res.append(node) #当栈的头部是数字时，说明左侧走到了尽头，将父节点的值添加到列表中
            return res
        return [first(root),middle(root),last(root)]

递归解法

class Solution:
    def threeOrders(self , root ):
        # write code here
        if root is None:
            return [None,None,None]
        def first(root,res = []):
            if not root:
                return
            res.append(root.val)
            first(root.left,res)
            first(root.right,res)
            return res
        def middle(root,res):
            if not root:
                return
            middle(root.left, res)
            res.append(root.val)
            middle(root.right, res)
            return res
        def last(root,res=[]):
            if not root:
                return
            last(root.left,res)
            last(root.right,res)
            res.append(root.val)
            return res
        return [first(root,[]),middle(root,[]),last(root,[])]