二叉树的前中后序遍历

先定义二叉树：

 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 PreorderTraversal(TreeNode root) {
        //定义一个链表数组
        var res=new List();
        if(root==null)//如果根节点为空，就返回
            return res;
            Transersal(root,res);
            return res;   
    }
   private void Transersal(TreeNode root,List res){
       if(root==null)
       return;
       res.Add(root.val);
       Transersal(root.left,res);
       Transersal(root.right,res);
   }
}
迭代
public class Solution {
    public IList PreorderTraversal(TreeNode root) {
        var res=new List();
        var stack=new Stack();
        if(root!=null)
         stack.Push(root);
         while(stack.Count>0){
             TreeNode node=stack.Peek();
             if(node!=null){
                 stack.Pop();
                

                if(node.right!=null)
                stack.Push(node.right);
                if(node.left!=null)
                stack.Push(node.left);

                 stack.Push(node);
                 stack.Push(null);
             }
             else{
                 stack.Pop();
                 node=stack.Peek();
                 stack.Pop();
                 res.Add(node.val);
             }
         }
           
            return res;
    }
}

中序遍历：

//递归
public class Solution {
    public IList PreorderTraversal(TreeNode root) {
        //定义一个链表数组
        var res=new List();
        if(root==null)//如果根节点为空，就返回
            return res;
            Transersal(root,res);
            return res;   
    }
   private void Transersal(TreeNode root,List res){
       if(root==null)
       return;
       Transersal(root.left,res);
         res.Add(root.val);
       Transersal(root.right,res);
   }
}

后序遍历：

//  递归
public class Solution {
    public IList PostorderTraversal(TreeNode root) {
        var res=new List();
        if(root==null)
        return res;
        Traversal(root,res);
        return res;

    }
    private void Traversal(TreeNode root,List res){
        if(root==null)
        return;
        Traversal(root.left,res);
        Traversal(root.right,res);
        res.Add(root.val);
    }
}

// 迭代
public class Solution {
    public IList PostorderTraversal(TreeNode root) {
        var res=new List();
        var stack=new Stack();
        if(root!=null)
         stack.Push(root);
         while(stack.Count>0){
             TreeNode node=stack.Peek();
             if(node!=null){
                 stack.Pop();
                 stack.Push(node);
                 stack.Push(null);

                if(node.right!=null)
                stack.Push(node.right);
                if(node.left!=null)
                stack.Push(node.left);
             }
             else{
                 stack.Pop();
                 node=stack.Peek();
                 stack.Pop();
                 res.Add(node.val);
             }
         }
       return res;
    }
}