day13: 第六章 二叉树part01 |二叉树的前序遍历,后序遍历,中序遍历,（递归。层序（广度）跟迭代遍历）

二叉树递归三部曲：

1. 确定递归函数的参数和返回值。

2. 确定终止条件

3.确定单层递归的逻辑

144.二叉树的前序遍历：中左右,递归：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }

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

145.二叉树的后序遍历:左右中

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

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

94.二叉树的中序遍历:左中右

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

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

层序：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //每次把一层的放进去，记录一个size.
        //二维数据
        List <List<Integer>> list = new ArrayList<List<Integer>>();
        if(root == null) return list;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            //二维数组中的其中一维
            List<Integer> item = new ArrayList<>();
            int size = que.size();

            while(size > 0){
                TreeNode temp = que.poll();
                item.add(temp.val);

                if(temp.left != null){ que.offer(temp.left);}
                if(temp.right != null){que.offer(temp.right);}

                size--;
            }
            list.add(item);
        }

        return list;
    }
}

一套代码打10个：

102.二叉树的层序遍历(opens new window)
107.二叉树的层次遍历II(opens new window)
199.二叉树的右视图(opens new window)
637.二叉树的层平均值(opens new window)
429.N叉树的层序遍历(opens new window)
515.在每个树行中找最大值(opens new window)
116.填充每个节点的下一个右侧节点指针(opens new window)
117.填充每个节点的下一个右侧节点指针II(opens new window)
104.二叉树的最大深度(opens new window)
111.二叉树的最小深度