226. Invert Binary Tree

226. Invert Binary Tree:题目链接

DFS-递归

class Solution {
    
    // 递归宏观语义：返回左右孩子互换的二叉树  时间复杂度O(N) 空间复杂度O(N)
    public TreeNode invertTree(TreeNode root) {
        if (root == null) { 
            return null;
        }
        TreeNode temp = root.left;  // 先用临时变量记住root的left
        root.left = invertTree(root.right); // root的左孩子变成已经交换好了的右子树
        root.right = invertTree(temp); // root的右孩子变成已经交换好了的左子树
        return root;
    }
}

BFS-层次遍历

在层次遍历出队时，将队首结点的左右孩子互换

class Solution {
    
    // BFS 时间复杂度O(N) 空间复杂度O(M)M:队列的长度
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode front = queue.poll();
            // 在将队首结点出队的时候 将队首结点的左右孩子 互换
            TreeNode temp = front.left;
            front.left = front.right;
            front.right = temp;
            if (front.left != null) {
                queue.offer(front.left);
            }
            if (front.right != null) {
                queue.offer(front.right);
            }
        }
        return root;
    }
}