給定一個二叉樹的根節點?root?，返回?它的?中序?遍歷?。

示例 1：

輸入：root = [1,null,2,3]

輸出：[1,3,2]

示例 2：

輸入：root = []

輸出：[]

示例 3：

輸入：root = [1]

輸出：[1]

提示：

• 樹中節點數目在范圍?[0, 100]?內
• -100 <= Node.val <= 100

進階:?遞歸算法很簡單，你可以通過迭代算法完成嗎？

思路：

二叉樹的中序遍歷的方法為：依次遍歷左子樹、根結點和右子樹，對于左子樹和右子樹使用同樣的方法遍歷。

遞歸的終止條件是當前結點為空。對于非終止條件，遞歸的做法如下。

對當前結點的左子樹調用遞歸。

將當前結點的結點值加入中序遍歷序列。

對當前結點的右子樹調用遞歸。

遍歷結束之后即可得到中序遍歷序列。

代碼：C#

public class Solution {

? ? public IList<int> InorderTraversal(TreeNode root) {

? ? ? ? IList<int> ans=new List<int>();//用于存儲遍歷結果

? ? ? ? Recursive(root,ans);//將根節點和結果列表傳入

? ? ? ? return ans;//返回最終結果

? ? }

? ? ? ? public void ?Recursive(TreeNode node,IList<int> ans)

? ? ? ? {

? ? ? ? ? ? if(node==null)

? ? ? ? ? ? return;//遞歸的結束條件為節點為空

? ? ? ? ? ? Recursive(node.left,ans);//先遞歸遍歷左子樹

? ? ? ? ? ? ans.Add(node.val);//將當前節點的值保存

? ? ? ? ? ? Recursive(node.right,ans);//在遞歸遍歷右子樹

? ? ? ? }

}