LeetCode热题100：31-40解析

36. 二叉树的中序遍历（二叉树/94）

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
假设：树中节点数目在范围 [0, 100] 内；-100 <= Node.val <= 100。
输入：root = [1,null,2,3]；输出：[1,3,2]。

【分析】
中序遍历：左子树->根节点->右子树
简单解法：递归算法。复杂解法：迭代算法。
知识点：（迭代算法中）当你的方法声明返回IList<int>，而内部返回的是List<int>时，这是完全合法的，因为List<int>实现了IList<int>接口，这是在C#标准库中定义的。在面向对象编程中，这是一种常见的做法，称为“编程到接口”（Program to Interface）。这样做的好处是提高了代码的灵活性和可扩展性，因为你的方法可以返回任何实现了IList<int>接口的具体类型，而不仅仅是List<int>。
Stack类：（迭代算法中）常用方法是Push，Pop，Peek（返回堆栈顶部的元素，但不将其移除），Contains，Count（没有括号），可用foreach。

/**
 * 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){
		List<int> res=new List<int>();
		Inorder(root,res);
		return res;
	}
	
	public void Inorder(TreeNode node, List<int> res){//要返回的变量通过参数传入，因为在函数内部也要做编辑
		if(node==null) return;
		Inorder(node.left,res);
		result.Add(node.val);
		Inorder(node.right,res);
	}
	
	
	//迭代算法（使用栈）
	public IList<int> InorderTraversal(TreeNode root){
		List<int> res=new List<int>();
		Stack<TreeNode> stack=new Stack<TreeNode>();
		TreeNode curr=root;
		while(curr!=null || stack.Count>0){
			while(curr!=null){//从根节点开始，不断地将左节点压入栈中
				stack.Push(curr);
				curr=curr.left;
			}//当左节点不存在时，内循环就不走了，下一句弹出的就是中间结点
			curr=stack.Pop();//内循环结束后弹出的顺序就是从最左向内
			res.Add(curr.val);
			curr=curr.right;//走到这里时，当前结点一定没有左节点了
		}
		return res;
	}
}