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

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

描述：给定一棵二叉树，分别按照二叉树先序，中序和后序打印所有的节点。

数据范围：0≤n≤1000，树上每个节点的val值满足 0≤val≤100

要求：空间复杂度 O(n)，时间复杂度 O(n)

思路：既然是二叉树那就递归，先序递归preorder，结果是preResult；中序递归midorder，结果是midResult；后序递归afterorder，结果是afterResult。

先序的结果是根节点，左子树，右子树的顺序，所以先序的代码就是先将根节点的值保存入preResult，再左子树先序递归preorder，然后右子树先序递归preorder，最后返回preResult

中序的结果是左子树，根节点，右子树的顺序，所以中序的代码就是先左子树中序递归midorder，再将根节点的值保存入midResult，然后右子树中序递归midorder，最后返回midResult

后序的结果是左子树，右子树，根节点的顺序，所以后序的代码就是先左子树后序递归afterorder，再右子树后序递归afterorder，然后将根节点的值保存入afterResult，最后返回afterResult

主函数只需要按顺序将三个结果append，然后返回即可

话说我已经完全忘记怎么用while循环取遍历二叉树了，算了，我工作的时候基本上也用不到二叉树。要用的时候，我再看评论区学习吧

# 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:
    preResult = []
    midResult = []
    afterResult = []
    def preorder(self,root):
        if root == None:
            return self.preResult
        self.preResult.append(root.val)
        self.preorder(root.left)
        self.preorder(root.right)
        return self.preResult
    def midorder(self,root):
        if root == None:
            return self.midResult
        self.midorder(root.left)
        self.midResult.append(root.val)
        self.midorder(root.right)
        return self.midResult
    def afterorder(self,root):
        if root == None:
            return self.afterResult
        self.afterorder(root.left)
        self.afterorder(root.right)
        self.afterResult.append(root.val)
        return self.afterResult
    def threeOrders(self , root: TreeNode) -> List[List[int]]:
        # write code here
        result = []
        result.append(self.preorder(root))
        result.append(self.midorder(root))
        result.append(self.afterorder(root))
        return result