LeetCode226. 翻转二叉树

方法1：递归。二叉树此类递归问题，要以根节点为目标点进行分析。

　　　思路1：首先分别翻转根节点的左右子树，然后交换左右子树的位置即可。

　　　思路2：也可以先交换左右子树的位置，然后再分别翻转根节点的左右子树。

方法2：BFS层序遍历

　　层序遍历树的所有节点，然后交换其左右节点即可。

方法3：只要能遍历二叉树的所有节点都可以解决，如前序遍历等。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        /**
         *  方法1.1 递归  先递归翻转 再交换
         */
        if (root == null)
            return null;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
        /**
         *  方法1.2 递归  先交换 再递归翻转
         */
        /*
        if (root == null) return null;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
        */
        /**
         *  方法2：BFS———层序遍历
         */
        /*
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();

                TreeNode temp = cur.left;
                cur.left = cur.right;
                cur.right = temp;

                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
        }
        return root;
        */
        /**
         * 方法3：非递归前序遍历
         */
        /*
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                TreeNode temp = cur.left;
                cur.left = cur.right;
                cur.right = temp;
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }
        return root;
        */
        /**
         * 方法4.非递归中序遍历 (有陷阱)
         */
        /*
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            TreeNode temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;
            //注意，这里是交换之后的，所以要修改
//            cur = cur.right;
            cur = cur.left;
        }
        return root;
        */
    }
}