Leetcode剑指Offer刷题 - 第六天

Leetcode剑指Offer刷题 - 第六天

 Leetcode剑指Offer刷题指南：

Leetcode剑指Offer刷题-学习计划目录_DEGv587的博客-CSDN博客

面试题32 - I. 从上到下打印二叉树

解法：层序遍历二叉树 BFS

class Solution {
    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }

        Queue queue = new linkedList<>();
        ArrayList list = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }

        int[] ret = new int[list.size()];
        for (int i = 0; i < list.size(); ++i) {
            ret[i] = list.get(i);
        }

        return ret;
    }
}

剑指 Offer 32 - II. 从上到下打印二叉树 II

解法一：BFS

class Solution {
    public List> levelOrder(TreeNode root) {
        Queue queue = new linkedList<>();
        List> lists = new ArrayList<>();
        if (root != null) {
            queue.add(root);
        }

        while (!queue.isEmpty()) {
            List list = new ArrayList<>();
            for (int i = queue.size(); i > 0; --i) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            lists.add(list);
        }

        return lists;
    }
}

解法二：递归循环

class Solution {
    List> ret=new ArrayList();
    public List> levelOrder(TreeNode root) {
        lei(root,0);
        return ret;
    }
    public void lei(TreeNode root,int k){
        if(root!=null){
            if(ret.size()<=k)ret.add(new ArrayList());
            ret.get(k).add(root.val);
            lei(root.left,k+1);
            lei(root.right,k+1);
        }
    }
}

剑指 Offer 32 - III. 从上到下打印二叉树 III

解法一：层序遍历 + 双端队列

class Solution {
    public List> levelOrder(TreeNode root) {
        Queue queue = new linkedList<>();
        List> ret = new ArrayList<>();
        if (root != null) queue.add(root);
        while (!queue.isEmpty()) {
            linkedList list = new linkedList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if (ret.size() % 2 == 0) {
                    // 偶数层 -> 队列尾部
                    list.addLast(node.val);
                } else {
                    // 奇数层 -> 队列头部
                    list.addFirst(node.val);
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            ret.add(list);
        }
        return ret;
    }
}

解法二：层序遍历 + 倒序

class Solution {
    public List> levelOrder(TreeNode root) {
        Queue queue = new linkedList<>();
        List> ret = new ArrayList<>();
        if (root != null) queue.add(root);
        while (!queue.isEmpty()) {
            List list = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            if (ret.size() % 2 == 1) {
                Collections.reverse(list);
            }
            ret.add(list);
        }
        return ret;
    }
}