LeeTCode226. 翻转二叉树

给你一棵二叉树的根节点root，翻转这棵树，并返回根节点root。

二叉树

递归：
1 输入值和返回值：
传入的是根节点，返回根节点
public TreeNode invert（TreeNode root）
2 递归结束条件：
父节点成功反转，父节点的左子树和右子树也成功反转
TreeNode keeper = root.left；
root.left = root.right;
root.right = keeper;
root = root.left;
3 每层递归逻辑

层序遍历：在while循环里加入左右子树交换即可。

//递归遍历
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        TreeNode keeper = root.right;
		root.right = root.left;
		root.left = keeper;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

//递归遍历
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        Deque queue = new ArrayDeque<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int n = queue.size();
            //tmp暂时存放从队列中获取的第一个树节点
            TreeNode tmp = queue.poll();
            //节点left暂时存放当前根节点的左子树
            //进行交换
            TreeNode left = tmp.left;
            tmp.left = tmp.right;
            tmp.right = left;
            if (tmp.left != null) queue.add(tmp.left);
            if (tmp.right != null) queue.add(tmp.right);
        }
        return root;
    }
}