LeetCode刷题Day13——二叉树（翻转二叉树、对称二叉树、二叉树的深度）

/**
 * <pre>
 * 1.递归法，可以采用先序遍历，后续遍历，层次遍历，但是不能采用中序遍历，因为中序遍历是左根右，即首先交换左节点的子节点，然后翻转根节点的左右节点，这个时候原本的左节点就变成了右节点，那么最后交换右子树的子节点时，其实还是交换的最开始的左节点，等于最开始根节点的左节点反转了两次，而右节点没有翻转
 * 2.迭代法
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/14 18:16
 */
public class 翻转二叉树226 {
    public TreeNode invertTree(TreeNode root) {
        turn(root);
        return root;
    }
    public void turn(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = tmp;
        turn(root.left);
        turn(root.right);
    }
    public TreeNode invertTree2(TreeNode root) {
        TreeNode node = root;
        Stack<TreeNode> stack = new Stack<>();
        while (node != null || !stack.empty()) {
            while (node != null) {
                TreeNode tmp = node.right;
                node.right = node.left;
                node.left = tmp;
                stack.push(node);
                node = node.left;
            }
            node = stack.pop().right;
        }
        return root;
    }
}

/**
 * <pre>
 * 1.自诩观察我们会发现如果二叉树对称，那么进行左右根和右左根遍历得出的结果是相同的（根左右根右左也相同）
 * 2.递归：如果左右子树对称，那么它们的各自的左右子树都跟另一棵树的右左子树对称
 * 3.迭代实现
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/14 23:39
 */
public class 对称二叉树101 {
    public boolean isSymmetric(TreeNode root) {
        List<Integer> leftList = new ArrayList<>();
        List<Integer> rightList = new ArrayList<>();
        postorder1(leftList, root);
        postorder2(rightList, root);
        return leftList.equals(rightList);
    }
    public void postorder1(List<Integer> res, TreeNode root) {
        if (root == null) {
            res.add(null);
            return;
        }
        res.add(root.val);
        postorder1(res, root.left);
        postorder1(res, root.right);
    }
    public void postorder2(List<Integer> res, TreeNode root) {
        if (root == null) {
            res.add(null);
            return;
        }
        res.add(root.val);
        postorder2(res, root.right);
        postorder2(res, root.left);
    }
    public boolean isSymmetric2(TreeNode root) {
        return check(root.left, root.right);
    }
    public boolean check(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        if (node1 == null || node2 == null) {
            return false;
        }
        return node1.val == node2.val && check(node1.left, node2.right) && check(node1.right, node2.left);
    }
    // 迭代版
    public boolean isSymmetric3(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
            if (node1 == null && node2 == null) {
                continue;
            }
            if (node1 == null || node2 == null || node1.val != node2.val) {
                return false;
            }
            queue.offer(node1.left);
            queue.offer(node2.right);
            queue.offer(node2.left);
            queue.offer(node1.right);
        }
        return true;
    }
}

/**
 * <pre>
 * 递归(深搜)：一个节点的高度等于其子节点的最大高度加1
 * 广搜：逐层往下，如果这一层有节点的话，将这一层节点的子节点入队，然后答案数+1，然后进入下一层，否则结束
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/15 0:48
 */
public class 二叉树的最大深度104 {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left) ;
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
    public int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size(); // 获得当前这一层的节点数
            while (size > 0) { // 取出这一层所有的节点，将它们各自的子节点入队
                TreeNode poll = queue.poll();
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
                size--;
            }
            ans++;
        }
        return ans;
    }
}

/**
 * <pre>
 * 深搜：遍历完整棵树，记录最小的长度
 * 广搜：逐层往下，直到第一次遇到叶子节点则结束
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/15 1:01
 */
public class 二叉树的最小深度111 {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1; // 叶子节点
        }
        int min = Integer.MAX_VALUE;
        // 只有节点不等于null才能递归，否则传递null会直接返回0，会导致min等于0，那么另一个节点不管是否有值min都等于0
        // 即最后结果为1
        // 但其实如果一个节点的left和right只有一个为null的话，这个节点并非叶子节点，即其结果也不是1，而是另一个不为null的节点的到叶子节点的距离+1，为了避免null节点扰乱min的值（min是用来求两个有效子节点返回结果的最小值，而null返回的结果是无效的），则需要非null才能进入递归
        if (root.left != null) {
            min = Math.min(minDepth(root.left), min);
        }
        if (root.right != null) {
            min = Math.min(minDepth(root.right), min);
        }
        return min + 1;
    }
    public int minDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int ans = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0){
                TreeNode poll = queue.poll();
                if (poll.left == null && poll.right == null) {
                    return ans;
                } else {
                    if (poll.left != null) {
                        queue.offer(poll.left);
                    }
                    if (poll.right != null) {
                        queue.offer(poll.right);
                    }
                    size--;
                }
            }
            ans++;
        }
        return ans;
    }
}