40、LeetCode-226.翻转二叉树

题目描述：

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

思路：

1）使用递归简单：使用了系统自带的 栈的数据结构

2）自己声明栈的数据结构，层序遍历，队列也可以！

代码：

1）递归反转

class Solution {
    public TreeNode invertTree(TreeNode root) {
        reverse(root);
        return root;
    }
    //递归，将传入的两个节点反转
    void reverse(TreeNode root){
        if(root == null) return;
        //交换节点
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        if(root.left != null) reverse(root.left);
        if(root.right != null) reverse(root.right);
    }
}

2）借助栈实现层序遍历：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        //使用迭代的方式,用栈实现
        if(root == null) return root;
        Stack stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            int size = stack.size();
            for(int i = 0;i < size;i++){
                TreeNode node = stack.pop();
                //按从左到右添加，就会从右到左弹出
                if(node.left != null) stack.push(node.left);
                if(node.right != null) stack.push(node.right);
                TreeNode temp = node.left;
                node.left = node.right;
                node.right = temp;
            }
        }
        return root;
    }
}