【力扣刷题|第十二天】二叉树的层序遍历

二叉树的层序遍历

力扣题目网址:二叉树的层序遍历

这个题我们可以使用队列的方式来进行层序遍历，先用一个队列存储根节点，然后一直循环，先获取队列中的节点的值，然后将队列中节点的左右节点存入队列，然后继续遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        while (!q.isEmpty()) {
            List<Integer> vals = new ArrayList<Integer>();
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                vals.add(node.val);
                if (node.left != null) {
                    q.add(node.left);
                }
                if (node.right != null) {
                    q.add(node.right);
                }
            }
            ans.add(vals);
        }
        return ans;
    }
}

二叉树的锯齿形层序遍历

力扣题目网址:二叉树的锯齿形层序遍历

这个题跟上一题差不多，只需要初始化一个布尔变量，当遍历的奇数层的时候顺序添加，遍历到偶数层的时候倒序添加,每次遍历完改变布尔值

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        boolean even = true;
        q.add(root);
        while (!q.isEmpty()) {
            List<Integer> vals = new ArrayList<Integer>();
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                vals.add(node.val);
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            if (!even) {
                Collections.reverse(vals);
            }
            ans.add(vals);
            even = !even;
        }
        return ans;
    }
}

找树左下角的值

力扣题目网址:找树左下角的值

这道题我们依旧可以使用第一个题的方法，层序遍历，然后返回最左边的那个数 ，但是这样速度太慢，我们看另一种方法，还是使用队列，这次我们先添加右子树，再添加左子树，那么当我们从队列当中取节点的时候，最先出来的就是右节点，那么我们只需要返回队列当中最后一个节点的值就可以。

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        TreeNode node = null;
        queue.add(root);
        while(!queue.isEmpty()) {
            node = queue.poll();
            if(node.right != null) queue.add(node.right);
            if(node.left != null) queue.add(node.left);
        }
        return node.val;
    }
}