翻转二叉树

题目描述：
翻转一棵二叉树。

示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1

Java代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //DFS
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        //交换当前节点的左右孩子
        TreeNode temp = root.right;
        root.right = root.left;
        root.left = temp;

        //递归交换当前节点的右孩子
        invertTree(root.right);
        //递归交换当前节点的左孩子
        invertTree(root.left);
        //函数返回时就表示当前节点和他的左右孩子已经交换完了
        return root;
    }
    
    //BFS
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        //将二叉树的节点逐层放入队列中，再迭代处理队列中的元素
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()) {
            //每次都从队列中拿出一个节点，并交换她的左右孩子
            TreeNode temp = queue.poll();
            TreeNode left = temp.left;
            temp.left = temp.right;
            temp.right = left;

            //如果当前节点的左孩子不为空，则放入队列等待后续处理
            if(temp.left != null) queue.add(temp.left);
            //如果当前节点的右孩子不为空，则放入队列等待后续处理
            if(temp.right != null) queue.add(temp.right);
        }

        return root;
    }
}