# 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
"""
  中序遍历就是：中-> 左 -> 右
  使用递归的思想来做
  当root节点不为空的时候，就去左节点，然后再将root节点的值添加进数组，再去右节点
"""
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []         # （1）建立返回值
        self.bl(root, ans)   # （2）递归调用
        return ans   # （3）返回值
    def bl(self, root:TreeNode, ans:List[int]):   # （1）创建递归函数
        if root == None: return    # （2）判断结束条件
        self.bl(root.left, ans)    # （3）进入左节点
        ans.append(root.val)       # （4）将节点值加入数组
        self.bl(root.right, ans)   # （5）进入右节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<int> InorderTraversal(TreeNode root) {
        IList<int> ans = new List<int>();   // （1）建立返回值
        bl(ans, root);                      // （2）递归调用
        return ans;                         //  (3）返回值
    }
    public static void bl(IList<int> ans, TreeNode root)  
    {                                   // （1）创建递归函数
        if (root == null) return;       // （2）判断结束条件
        bl(ans, root.left);             // （3）进入左节点
        ans.Add(root.val);              // （4）将节点值加入数组
        bl(ans, root.right);            // （5）进入右节点
    }
}