226. Invert Binary Tree

就三种方法

naive递归

def invertTree(self, root):
    """
    :type root: TreeNode
    :rtype: TreeNode
    """
    if not root: return 
    root.left, root.right = root.right, root.left
    self.invertTree(root.left)
    self.invertTree(root.right)
    return root

下->上交换

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tmp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(tmp);
    return root;
}

没有返回值，先交换后递归。上->下交换

public void Mirror(TreeNode root) {
    if (root == null) return;
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    Mirror(root.left);
    Mirror(root.right);
}

BFS:

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
        TreeNode node = q.poll();
        TreeNode tmp = node.right;
        node.right = node.left;
        node.left = tmp;

        if (node.left != null) q.offer(node.left);
        if (node.right != null) q.offer(node.right);
    }
    return root;
}