LeetCode(树)----226. 翻转二叉树

题目

翻转一棵二叉树。

示例：
输入：

输出：

思路：

这道题主要是为了翻转所有的左右子节点，那么我们只要遍历出所有的节点，翻转左右子树即可。（这里的遍历方法有前序遍历，中序遍历，后序遍历（这三种为递归实现），层序遍历（这种为迭代实现））

解法一：前序遍历（后序遍历的解法上与之类似，不过中序遍历有所注意）

class Solution {
	 //前序遍历
	 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;
	}
}

解法二：中序遍历

中序遍历使用时，我们先遍历出了左子树，那么左右子树交换时，我们要注意最后的递归表达式还是递归左子树, 因为现在的左子树即为右子树

class Solution {
	public TreeNode invertTree(TreeNode root) {
		if(root == null) return root;
		
		//中序遍历的时候,要注意这时已先遍历出左子树
		invertTree(root.left);
		
		//左右交换
		TreeNode tmp = root.left;
		root.left = root.right;
		root.right = tmp;
		
		//此时root.left才是它的右子树
		invertTree(root.left);
		
		return root;
	}
}

解法三：层序遍历（迭代实现）

层序遍历一般使用队列存储，因为每个节点都遵循先进先出原则（即弹出根节点时，顺便把左右节点入队）

class Solution {
    //层序遍历出所有的节点,然后交换它的左右子树
	public TreeNode invertTree(TreeNode root) {
		if(root == null) return root;
		
		Queue<TreeNode> queue = new LinkedList<>(); 
		queue.add(root);
		
		while(!queue.isEmpty()) {
			TreeNode node = queue.poll();
			
			TreeNode tmp = node.left;
			node.left = node.right;
			node.right = tmp;
			
			if(node.left != null) {
				queue.add(node.left);
			}
			if(node.right != null) {
				queue.add(node.right);
			}

		}
		
		
		return root;
	}
}