day15 打卡102. 二叉树的层序遍历 226.翻转二叉树 101.对称二叉树 2

102. 二叉树的层序遍历

102题目链接

1.使用队列

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        // 记录每一层有几个元素
        int size = 1;
        while (!que.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            size = que.size();
            while (size>0) {
                TreeNode cur = que.poll();
                list.add(cur.val);
                if (cur.left != null) que.offer(cur.left);
                if (cur.right != null) que.offer(cur.right);
                size--;
            }
            result.add(list);
        }
        return result;
    }
}

2.递归法

class Solution {
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return result;
        order(root, 0);
        return result;
    }

    public void order(TreeNode cur, int deep) {
        if (cur == null) return;
        deep++;

        if (result.size() < deep) {
            result.add(new ArrayList<Integer>());
        }
        result.get(deep-1).add(cur.val);

        order(cur.left, deep);
        order(cur.right, deep);
    }
}

226.翻转二叉树

226题目链接

1.递归法

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        invert(root);
        return root;
    }

    public void invert(TreeNode cur) {
        if (cur.left == null && cur.right == null) return;

        TreeNode temp = cur.left;
        cur.left = cur.right;
        cur.right = temp;

        if (cur.left != null) invert(cur.left);
        if (cur.right != null) invert(cur.right);
    }
}

2.使用队列，层次遍历

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        int size = 1;
        while (!que.isEmpty()) {
            size = que.size();
            while (size>0) {
                TreeNode cur = que.poll();
                swap(cur);
                if (cur.left != null) que.offer(cur.left);
                if (cur.right != null) que.offer(cur.right);
                size--;
            }
        }
        return root;
    }

    public void swap(TreeNode node) {
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

101.对称二叉树 2

101题目链接

1.递归法

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return compare(root.left, root.right);
    }

    public boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right != null) return false;
        else if (left != null && right == null) return false;
        else if (left == null && right == null) return true;
        else if (left.val != right.val) return false;

        boolean outside = compare(left.left, right.right);
        boolean inside = compare(left.right, right.left);
        return outside && inside;
    }
}

2.使用双端队列

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offerFirst(root.left);
        deque.offerLast(root.right);
        while (!deque.isEmpty()) {
            TreeNode left = deque.pollFirst();
            TreeNode right = deque.pollLast();

            if (left == null && right == null) continue;

            if (left == null && right != null) return false;
            else if (left != null && right == null) return false;
            else if (left.val != right.val) return false;

            deque.offerFirst(left.right);
            deque.offerFirst(left.left);
            deque.offerLast(right.left);
            deque.offerLast(right.right);
        }
        return true;
    }
}

参考资料

代码随想录