Leetcode刷题100天—226. 翻转二叉树（二叉树）—day03

我会带着你远行 2022-09-02 11:39 179阅读 0赞

前言：

> 作者：神的孩子在歌唱  
> 大家好，我叫运智

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY1NDExNA_size_16_color_FFFFFF_t_70]

### 翻转一棵二叉树。 ###

**示例：**

输入：

4
       /   \
      2     7
     / \   / \
    1   3 6   9

输出：

4
       /   \
      7     2
     / \   / \
    9   6 3   1

> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/invert-binary-tree  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 代码 ###

此题有四种解法，前序，后序，中序，层序遍历，前三种用了递归方法实现的

/* * 1 * https://leetcode-cn.com/problems/invert-binary-tree/ * 翻转一颗二叉树就是将其所有左右节点的左右子树都交换，也就是需要遍历所有节点，前序遍历 */
    public class TreeNode { 
    	int val;
    	TreeNode left;
    	TreeNode right;
    	TreeNode(int val) {  this.val = val; }
    }
    public class _226_翻转二叉树<E> { 
    	public TreeNode invertTree(TreeNode root) { 
    // 前序遍历，先访问自己，在访问左右
    		if (root==null) return root;
    // 先遍历头节点的子树
    		TreeNode tmp=root.left;
    		root.left=root.right;
    		root.right=tmp;
    // 再用递归方法遍历左右子树，先遍历左或者右都没关系
    		invertTree(root.left);
    		invertTree(root.right);
    		return root;
    	}
    	public TreeNode invertTree1(TreeNode root) { 		
    // 方法二:后序遍历，先访问左右，在访问自己
    		if (root==null) return root;
    // 先用递归方法遍历左右子树，先遍历左或者右都没关系
    		invertTree(root.left);
    		invertTree(root.right);
    // 在将左右子树调换
    		TreeNode tmp=root.left;
    		root.left=root.right;
    		root.right=tmp;
    
    		return root;
    	}
    	public TreeNode invertTree2(TreeNode root) { 
    // 方法三:中序遍历，先访问左，在自己（头节点），在右
    		if (root==null) return root;
    // 先用递归方法遍历左子树
    		invertTree(root.left);
    		
    // 在将左右子树调换
    		TreeNode tmp=root.left;
    		root.left=root.right;
    		root.right=tmp;
    // 这里注意不能写right，因为上边已经将左右子树调换了,right已经变成left了。
    		invertTree(root.left);
    		return root;
    	}
    	public TreeNode invertTree3(TreeNode root) { 
    // 方法四:层序遍历,从上到下，从左到右一次访问每一个节点
    		if (root==null) return root;
    // 创建队列，队列里面放节点TreeNode
    		Queue<TreeNode> queue=new LinkedList<>();
    // 将根节点入队
    		queue.offer(root);
    // 循环遍历,只要队列不为空，我就不断去除队列的头节点
    		while(!queue.isEmpty()) { 
    // 出队
    			TreeNode node=queue.poll();
    // System.out.print(node.element);
    // 将队头里面的元素左右交换
    			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;	
    	}	
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114  
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY1NDExNA_size_16_color_FFFFFF_t_70]: /images/20220829/ef51424497a84e15ad6038210383fede.png