一、 二叉树的前序遍历

image.png

前序遍历的输入顺序为：A-B-D-F-G-H-I-E-C
递归法

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        pre(root,list);
        return list;
    }
    //前序遍历
    void pre(TreeNode root,List<Integer> list){
        //当节点为空时，返回
        if(root == null){
            return;
        }
        list.add(root.val);     //先用list记录当前节点值
        pre(root.left,list);    //递归遍历节点的左子树
        pre(root.right,list);   //递归遍历节点的右子树
    }
}

迭代法

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        
        //Deque是双端队列，可以在两端插入删除元素
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                res.add(node.val);  //添加该节点值
                stack.push(node);   //将该节点压入队列中
                node = node.left;   //如果node.left存在，则重复第二个while循环
            }
            node = stack.pop(); //最近压入队列中的节点出队列
            node = node.right;
        }
        return res;
    }
}

二、二叉树的中序遍历

image.png

中序遍历的输入顺序为：F-D-H-G-I-B-E-A-C
递归法

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        mid(root,list);
        return list;
    }
    void mid(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        mid(root.left,list);    //直接递归到最左节点
        list.add(root.val);     //添加该节点的值
        mid(root.right,list);   //再递归右子树
    }
}

迭代法

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stk = new LinkedList<TreeNode>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {  //当压入到最左节点时停止
                stk.push(root);     //不断压入
                root = root.left;
            }
            root = stk.pop();   //通过出队列，节点不断往上走
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

三、二叉树的后序遍历

image.png

后序遍历的输入顺序为：F-H-I-G-D-E-B-C-A
递归法

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        mid(root,list);
        return list;
    }
    void mid(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        mid(root.left,list);    //直接递归到最左节点
        mid(root.right,list);   //再看右子树
        list.add(root.val);     //最后添加该节点的值
    }
}

四、二叉树的层序遍历

image.png

层序遍历
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
广度优先搜索BFS

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list1= new ArrayList<List<Integer>>();
        if(root == null){
            return list1;
        }
        //BFS
        Queue<TreeNode> queue = new LinkedList<TreeNode>(); //单端队列，先进先出
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> list2= new ArrayList<Integer>();
            int size = queue.size();    //size为当前队列的长度
            for(int i=1;i<=size;i++){
                TreeNode node = queue.poll(); //将一个节点出队列
                list2.add(node.val);    //添加该节点的值
                if(node.left != null){  //如果有左子树，左子树进队列
                    queue.add(node.left);
                }
                if(node.right != null){ //如果有右子树，右子树进队列
                    queue.add(node.right);
                }
            }
            //在一个for循环后，这同一层的节点值都在lsit2中了
            list1.add(list2);
        }
        return list1;
    }
}