package 二叉树.BT;
import java.util.LinkedList;
import java.util.Queue;
/**
 * https://leetcode-cn.com/problems/invert-binary-tree/
 * 题意，将所有结点进行左右结点数据进行交换（这里咱只需拿到所有结点即可~前序、中序、后序（递归）、层序（迭代）都可以拿到所有结点）
 * 
 * @author Huangyujun
 *
 */
public class _226_翻转二叉树 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {
        }
        TreeNode(int val) {
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    //前序遍历
    public TreeNode invertTree1(TreeNode root) {
        if(root == null)    return root;
        //前序遍历，首先拿到自己root[题意，交换当前结点的左右结点数据]
        TreeNode tmp = new TreeNode();
        tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    // 中序遍历
    public TreeNode invertTree2(TreeNode root) {
        if (root == null)
            return root;
        invertTree(root.left);
        // 前序遍历，首先拿到自己root[题意，交换当前结点的左右结点数据]
        TreeNode tmp = new TreeNode();
        tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        //这样写就出错了，没有很好理解递归的含义:再次 调用函数是为了递归进行找子结点（子树）
        //上面先 invertTree(root.left); 递归进左子树，然后进行交换，
        //（右子树的位置交换到左边了），若是还写invertTree(root.right); 又是一次递归进去左子树（重复了，而且还不给右子树机会）
//        invertTree(root.right);
        //修改：
        invertTree(root.left);
        return root;
    }
    // 层序遍历
    public TreeNode invertTree(TreeNode root) {
        if (root == null)    return null;
        Queue queue = new LinkedList();
        queue.offer(root);
        // 只要队列不为空：就不断的出队，然后入队左右子节点
        while (!queue.isEmpty()) {
            TreeNode node =  (TreeNode) queue.poll();
            //拿到当前结点（进行交换左右结点）
            TreeNode tmp = new TreeNode();
            tmp = node.left;
            node.left = node.right;
            node.right = tmp;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return root;
    }
}