day14| 94.二叉树的中序遍历；144.二叉树的前序遍历；145.二叉树的后序遍历

94. 二叉树的中序遍历

思路：

1. 找出重复的子问题

　　这个重复的子问题是：先遍历左子树、再取根节点、最后遍历右子树

2. 确定终止条件

　　当节点为空是，返回

代码如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:

    def inOrder(self, root:TreeNode, res):
        if root == None:
            return
        self.inOrder(root.left, res)
        res.append(root.val)
        self.inOrder(root.right, res)

    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.inOrder(root, res)
        return res

144. 二叉树的前序遍历

同上一题，改一改append和函数递归调用的顺序即可

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res=[]
        self.midOrder(root,res)
        return res
    

    def midOrder(self,root:TreeNode,res):
        if root == None:
            return
        res.append(root.val)
        self.midOrder(root.left,res)
        self.midOrder(root.right,res)

145. 二叉树的后序遍历

同样，改一改顺序即可

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res=[]
        self.postOrder(root,res)
        return res
    

    def postOrder(self,root:TreeNode,res):
        if root == None:
            return
        self.postOrder(root.left,res)
        self.postOrder(root.right,res)
        res.append(root.val)