二叉树四种遍历

遍历描述

前序遍历：先根节点，再左子树，最后右子树；上图的访问结果为：GDAFEMHZ。

中序遍历：先左子树，再根节点，最后右子树；上图的访问结果为：ADEFGHMZ。

后序遍历：先左子树，再右子树，最后根节点，上图的访问结果为：AEFDHZMG。

层次遍历：上图的访问结果为：GDMAFHZE。

二叉树的前序遍历

public int[] preorderTraversal (TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        dfs(list,root);
        int[] arr = list.stream().mapToInt(num -> Integer.valueOf(num)).toArray();
        return arr;
    }

    public void dfs(List<Integer> list,TreeNode root){
        if(root==null){
            return;
        }else{
            list.add(root.val);
            dfs(list,root.left);
            dfs(list,root.right);
        }
    }

二叉树的中序遍历

public int[] inorderTraversal (TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        dfs(list,root);
        int[] ints = list.stream().mapToInt(Integer::valueOf).toArray();
        return ints;
    }

    public void dfs(List<Integer> list,TreeNode root){
        if(root==null){
            return;
        }
        dfs(list,root.left);
        list.add(root.val);
        dfs(list,root.right);
    }

二叉树的后序遍历

public int[] postorderTraversal (TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        dfs(list,root);
        int[] ints = list.stream().mapToInt(Integer::valueOf).toArray();
        return ints;
    }

    public void dfs(List<Integer> list, TreeNode root){
        if(root==null){
            return;
        }
        dfs(list,root.left);
        dfs(list,root.right);
        list.add(root.val);
    }

二叉树的层次遍历实现

public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        bfs(lists,root,0);
        return lists;
    }
    public void bfs(ArrayList<ArrayList<Integer>> lists,TreeNode root,int level){
        if(root==null){
            return;
        }
        if(level >= lists.size()){
            lists.add(new ArrayList<Integer>());
        }
        lists.get(level).add(root.val);
        bfs(lists,root.left,level+1);
        bfs(lists,root.right,level+1);
    }