leetcode226.翻转二叉树

难度：简单
题目：翻转一颗二叉树

对于二叉树的题，很容易想到的就是使用递归。从题目中可以看出，将每个结点进行翻转。因此我们的思路是：先将根结点的左右子树进行翻转，然后依次递归下去进行翻转：
代码一：

class Solution{
    public TreeNode invertTree(TreeNode root){
        if(root == null) return null;
        //将左右子树进行交换
        TreeNode tmp=root.right;
        root.right=root.left;
        root.left=tmp;
		//递归交换当前结点的右子树
        invertTree(root.right);
        //递归交换当前结点的左子树
        invertTree(root.left);
        return root;

    }
}

代码二：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        TreeNode left= invertTree(root.left);
        TreeNode right=invertTree(root.right);
        root.left=right;
        root.right=left;
        return root;
    }
}

class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) {
return null;
}
//将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
LinkedList queue = new LinkedList();
queue.add(root);
while(!queue.isEmpty()) {
//每次都从队列中拿一个节点，并交换这个节点的左右子树
TreeNode tmp = queue.poll();
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;
}

}