前序遍历（时间复杂度O(n),空间复杂度O(n)）--使用栈

  public class TreeNode {
      public int val;
     public TreeNode left;
      public TreeNode right;
     public TreeNode(int x) { val = x; }
}
public class Solution 
{
/// <summary>
    /// 前序遍历
    /// </summary>
    /// <param name="root"></param>
    /// <returns></returns>
    public IList<int> PreorderTraversal(TreeNode root)
   {
       
        Stack<TreeNode> tempStack = new Stack<TreeNode>();
        IList<int> preorder = new List<int>();
         if(root == null) return preorder;
        tempStack.Push(root);
        while (tempStack.Count>0)
        { 
            TreeNode temp = tempStack.Peek();
           preorder.Add(tempStack.Pop().val); 
           //先添加右边
           if (temp.right != null)
           {
               tempStack.Push(temp.right); 
           }

           if (temp.left != null)
           {
                tempStack.Push(temp.left); 
           }
        }

        return preorder;
    }
}

中序--递归

时间复杂度：O(n)
空间复杂度：最坏情况下需要空间O(n)，平均情况为O(log⁡n)

 public class TreeNode {
     public int val;
     public TreeNode left;
     public TreeNode right;
     public TreeNode(int x) { val = x; }
}
public class Solution {
   /// <summary>
    /// 中序遍历
    /// </summary>
    /// <param name="root"></param>
    /// <returns></returns>
    public IList<int> InorderTraversal(TreeNode root) 
    {
        IList<int> res = new List<int>();
        InorderHelp(root, res);
        return res;
    }

    void InorderHelp(TreeNode node,IList<int> res)
    {
        if (node != null)
        {
            if (node.left != null)
                InorderHelp(node.left, res);
            res.Add(node.val);
            if (node.right != null)
                InorderHelp(node.right, res);
        }
    }
}

中序--栈

空间复杂度O(n)，时间复杂度O(n)

    public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
 }
public class Solution {
   public IList<int> InorderTraversal(TreeNode root)
    {
        IList<int> res = new List<int>();
        Stack<TreeNode> tempStack = new Stack<TreeNode>();
        TreeNode curr = root;
        while (curr != null||tempStack.Count>0)
        {
            while (curr != null)
            {
                tempStack.Push(curr);
                curr = curr.left;
            }

            curr = tempStack.Pop();
            res.Add(curr.val);
            curr = curr.right;
        }
        return res;
    }
}

后序遍历 --栈

空间复杂度O(n)，时间复杂度O(n)

 public class TreeNode {
    public int val;
   public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class Solution {
    public IList<int> PostorderTraversal(TreeNode root) {
     IList<int> res = new List<int>();
        if (root == null)
        {
            return res;
        }
        Stack<TreeNode> treeStack = new Stack<TreeNode>();
        treeStack.Push(root);
        TreeNode node = null;
        while (treeStack.Count>0)
        {
            node = treeStack.Pop();
            res.Insert(0,node.val);//每次取出插入开始位置
            if (node.left!=null)//先压入左节点
            {
                treeStack.Push(node.left);
            }
            if (node.right!=null)//再压入右节点
            {
                treeStack.Push(node.right);
            }
        }

        return res;
    }
    }