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