二叉树结点结构

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val=x;
    }
    @Override
    public String toString(){
        return "val: "+val;
    }
}

访问函数

public void visit(TreeNode node){
    System.out.print(node.val+" ");
}

先序遍历

递归

public void preOrderRecursion(TreeNode node){
    if (node == null)
        return;
    visit(node);
    preOrderRecursion(node.left);
    preOrderRecursion(node.right);
}

非递归

利用栈来实现

public List<Integer> preorderTraversal(TreeNode root){
    List<Integer> resultList = new ArrayList<>();
    Stack<TreeNode> treeNodeStack = new Stack<>();
    if (root == null)
        return resultList;
    treeNodeStack.push(root);
    while (!treeNodeStack.isEmpty()){
        TreeNode temp = treeNodeStack.pop();
        if (temp!=null){
            resultList.add(temp.val);//访问根节点
            treeNodeStack.push(temp.right);//入栈右孩子
            treeNodeStack.push(temp.left);//入栈左孩子    
        }
    }
        return resultList;
}

中序遍历

递归

public void inOrderRecursion(TreeNode node){
    if(node==null) //如果结点为空则返回
        return;
    preOrderRecursion(node.left);//访问左孩子
    visit(node);//访问根节点
    preOrderRecursion(node.right);//访问右孩子
    }

非递归

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();

    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur = root;

    while(cur!=null || !stack.empty()){
        while(cur!=null){
            stack.add(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        list.add(cur.val);
        cur = cur.right;
    }

    return list;
}

后序遍历

    /**
     * 非递归后序遍历
     * */
    public List<Integer> postOrderNonCur(TreeNode root){
        List<Integer> resultList=new ArrayList<>();
        if(root==null)
            return resultList;
        Map<TreeNode,Integer> visitedMap=new HashMap<>();
        Stack<TreeNode> toBeVisitedStack=new Stack<>();
        toBeVisitedStack.push(root);
        while(!toBeVisitedStack.isEmpty()){
            TreeNode tempNode=toBeVisitedStack.peek(); //注意这里是peek而不是pop
            if(tempNode.left==null && tempNode.right==null){ //如果没有左右孩子则访问
                resultList.add(tempNode.val);
                visitedMap.put(tempNode, 1);
                toBeVisitedStack.pop();
                continue;
            }else if(!((tempNode.left!=null&&visitedMap.get(tempNode.left)==null )|| (tempNode.right!=null && visitedMap.get(tempNode.right)==null))){
                //如果节点的左右孩子均已被访问            
                resultList.add(tempNode.val);
                toBeVisitedStack.pop();
                visitedMap.put(tempNode, 1);
                continue;
            }
            if(tempNode.left!=null){
                while(tempNode.left!=null && visitedMap.get(tempNode.left)==null){//左孩子没有被访问
                    toBeVisitedStack.push(tempNode.left);
                    tempNode=tempNode.left;
                }
            }
            if(tempNode.right!=null){
                if(visitedMap.get(tempNode.right)==null){//右孩子没有被访问
                    toBeVisitedStack.push(tempNode.right);
                }               
            }
        }
        return resultList;
    }

也可以用一个取巧的办法，先采用类似先序遍历，先遍历根节点再右孩子最后左孩子，再把遍历的序列逆转即可得到后序遍历

public List<Integer> postorderTraversal(TreeNode root) {
    Deque<TreeNode> stack = new LinkedList<>();
    stack.push(root);
    List<Integer> ret = new ArrayList<>();
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node != null) {
            ret.add(node.val);
            stack.push(node.left);
            stack.push(node.right);
        }
    }
    Collections.reverse(ret);
    return ret;
} 

层序遍历

层序遍历也即宽度优先搜索，一层一层搜索，非递归代码如下：

public List<Integer> levelOrder(TreeNode root){
    List<Integer>> resultList = new ArrayList<>();
    if (root == null)
        return resultList;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()){
        TreeNode temp = queue.poll();
        if (temp !=null){
            resultList.add(temp.val);
            queue.add(temp.left);
            queue.add(temp.right);
        }
    }
    return  resultList;
}

或

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> resultList=new ArrayList<>();
    int levelNum=0;//记录某层具有多少个节点
    Queue<TreeNode> treeQueue=new LinkedList<>();
    treeQueue.add(root);
    while(!treeQueue.isEmpty()){
        levelNum=treeQueue.size();
        List<Integer> levelList=new ArrayList<>();
        while(levelNum>0){
            TreeNode tempNode=treeQueue.poll();
            if(tempNode!=null){
                levelList.add(tempNode.val);
                treeQueue.add(tempNode.left); 
                treeQueue.add(tempNode.right);
            }
            levelNum--;
        }
        if(levelList.size()>0) 
            resultList.add(levelList);
    }
    return resultList;        
}

Q.E.D.