6.4 反转二叉树——【LeetCode】

package com.tree.java;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.linkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;


public class seven {

	//方法一：递归DFS
	public TreeNode invertTree(TreeNode root) {
		if(root == null) {
			return null;
		}
		invertTree(root.left);//这里不好理解的话 可以以题中的2处为例，当root==2结点，此时继续递归 root==1 继续返回null...
		invertTree(root.right);
		swapChildren(root);
		return root;
	}

	private void swapChildren(TreeNode root) {
		TreeNode tmp = root.left;
		root.left = root.right;
		root.right = tmp;
	}
	
	//方法二：BFS
	public TreeNode invertTree1(TreeNode root) {
		if(root == null) {
			return null;
		}
		ArrayDeque deque = new ArrayDeque<>();//临时存储每一行的结点
		deque.offer(root);
		while(!deque.isEmpty()) {
			int size = deque.size();
			while(size > 0) {
				TreeNode node = deque.poll();
				
				swap(node);
				
				//提前添加上下一行的所有结点到deque中，为下一次while循环做准备
				if(node.left != null) {
					deque.offer(node.left);
				}
				if(node.right != null) {
					deque.offer(node.right);
				}
				size--;
			}
		}
		return root;
		
	}

	private void swap(TreeNode node) {
		 TreeNode temp = node.left;
		 node.left = node.right;
		 node.right = temp;
	}
	
	
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
     }
 }