class Solution 
{
	/**
	 * 层次遍历
	 * @param root
	 * @return
	 */
	 public TreeNode invertTree_bfs(TreeNode root) 
	 {
		 if(root == null)
		 {
			 return root;
		 }
		 else
		 {
			 Queue<TreeNode> queue = new LinkedList<>();
			 queue.add(root);
			 while(!queue.isEmpty())
			 {
				 TreeNode pNode = queue.poll();
				 TreeNode tempNode = pNode.left;
				 pNode.left = pNode.right;
				 pNode.right = tempNode;
				 
				 if(pNode.left!=null)
				 {
					 queue.add(pNode.left);
				 }
				 if(pNode.right!=null)
				 {
					 queue.add(pNode.right);
				 }
			 }
			 return root;
		 }
	 }
	 
	 
	/**
	 * 先序遍历的方法
	 * @param root
	 * @return
	 */
    public TreeNode invertTree(TreeNode root) 
    {
    	if(root!=null)
    	{
    		TreeNode tempNode = root.left;
    		root.left = root.right;
    		root.right = tempNode;
    		invertTree(root.left);
    		invertTree(root.right);
    		return root;
    	}
    	
    	return null;
    }
}