代码随想录算法训练营第15天

今日任务

● 层序遍历 10 ● 226.翻转二叉树 ● 101.对称二叉树 2

链接：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv (opens in a new tab)

层序遍历 10

队列先进先出，符合一层一层遍历的逻辑，而栈先进后出，适合模拟深度优先遍历的逻辑。

自己想法

我这里用null来隔开每一层，这样就不用记录每一层的节点数了。

当然也可以记录每一层的节点数，然后用for循环来遍历每一层。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> layer = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        
        // 初始判断：树空？
        if(root != null) {
            queue.offer(root);
            queue.offer(null);  // 压入null表示隔开这一层
        }
        else return ans;
        // 遍历
        while(!queue.isEmpty()) {
            if(queue.peek() != null) {
                // 顶部非空，正在遍历这一层
                layer.add(queue.peek().val);  // 当前节点入layer
                System.out.println(layer);
                if(queue.peek().left != null) queue.offer(queue.peek().left);  // 压入左
                if(queue.peek().right != null) queue.offer(queue.peek().right);  // 压入右
                queue.poll();  // 弹出顶
            }
            else {
                // 顶部空，这一层遍历完毕
                System.out.println(layer);
                ans.add(layer);  // 当前layer入ans
                layer = new ArrayList<>();  // 当前layer清空
                queue.poll();  // 弹出空
                if(!queue.isEmpty()) queue.offer(null);
            }
        }
        return ans;
    }
}

题解想法

如高亮行(11行)所示，进入for时统计queue的size，这样就能遍历每一层了。

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

226.翻转二叉树

自己想法

class Solution {
    public TreeNode invertTree(TreeNode root) {
        invert(root);
        return root;
    }
    public void invert(TreeNode node) {
        if(node == null) return;
        else {
            invert(node.left);
            invert(node.right);
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
    }
}

101.对称二叉树 2

自己想法

层序遍历，每一层判断是否对称。

注意存在以下情况，不能用刚刚的加null标志判断层结束了，因为null节点也要加入layer，判断是否对称。因此这里使用了forf循环来遍历每一层。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        List<Integer> layer = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        
        // 初始判断：树空？
        if(root != null) {
            queue.offer(root);
        }
        else return true;
        // 遍历
        while(!queue.isEmpty()) {
            int size = queue.size();
 
            for(int i = 0; i < size; i++) {
                if(queue.peek() != null) {
                    layer.add(queue.peek().val);  // 当前节点入layer
                    queue.offer(queue.peek().left);  // 压入左
                    queue.offer(queue.peek().right);  // 压入右
                }
                else {
                    layer.add(null);
                }
                queue.poll();  // 弹出顶
            }
 
            System.out.println(layer);
            for(int i = 0; i < layer.size() / 2; i++) {
                if(layer.get(i) != layer.get(layer.size() - i -1)) return false;
            }
            layer = new ArrayList<>();  // 当前layer清空
        }
        return true;
    }
}

题解想法

递归法

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        else return invert(root.left, root.right);
    }
    // 1.返回值：是否对称
    public boolean invert(TreeNode left, TreeNode right) {
        // 2.终止条件
        if(left == null && right != null) return false;
        if(left != null && right == null) return false;
        if(left == null && right == null) return true;
        if(left.val != right.val) return false;
        // 3.递归逻辑
        boolean outside = invert(left.left, right.right);
        boolean inside = invert(left.right, right.left);
        if(outside && inside) return true;
        return false;
    }
}