每日刷题：第三十二天 翻转二叉树

思路：使用层序遍历，对于每一个结点，交换他们的两个子节点就好

通过代码（java）：

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root)
    {
        if(root == null) return root;
        //层序遍历，对于每个结点都交换子节点
        Queue queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty())
        {
            TreeNode node = queue.poll();
            //左右结点入队列
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            //交换
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
        }
        return root;
    }
}

另：看了题解，说前序后序也可以，这里再次练习了一次前序遍历的迭代法，但我觉得这道题目使用层序遍历是最直观的

前序遍历的迭代法

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root)
    {
       if(root == null) return root;
        //前序遍历
        Stack stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty())
        {
            TreeNode node = stack.pop();
            if (node != null)
            {
                //依次入栈
                if (node.right != null) stack.push(node.right);
                if (node.left != null) stack.push(node.left);
                stack.push(node);
                stack.push(null);
            }else
            {
    
                //d出要的元素
                TreeNode treeNode = stack.pop();
                //翻转该节点的两个子节点
                TreeNode temp = treeNode.left;
                treeNode.left = treeNode.right;
                treeNode.right = temp;
                
            }
        }
        return root;
    }
}