import java.util.*;
/**
* @author : xfhy
* Create time : 2020年10月21日08:56:09
* Description : 226. 翻转二叉树
* source : https://leetcode-cn.com/problems/invert-binary-tree/
*/
public class Solution {
public static 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;
}
}
/**
* 思路: 直接将左右子树交换即可,递归下去
*/
public static TreeNode invertTree(TreeNode root) {
invertHelper(root);
return root;
}
private static void invertHelper(TreeNode root) {
if (root == null) {
return;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertHelper(root.left);
invertHelper(root.right);
}
public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
if (inputList == null || inputList.isEmpty()) {
return null;
}
TreeNode node = null;
Integer data = inputList.removeFirst();
if (data != null) {
node = new TreeNode(data);
node.left = createBinaryTree(inputList);
node.right = createBinaryTree(inputList);
}
return node;
}
public static void main(String[] args) {
/*LinkedList<Integer> integers = new LinkedList<>(Arrays.asList(5, 4, 11, 7, null, null, 2, null, null, null, 8, 13, null, null, 4,
5, null, null, 1));*/
/*LinkedList<Integer> integers = new LinkedList<>(Arrays.asList(3, 2, 9, null, null, 10, null,
null, 8, null, 4));*/
LinkedList<Integer> integers = new LinkedList<>(Arrays.asList(7, 3, null, null, 15, 9, null, null, 20));
TreeNode binaryTree = createBinaryTree(integers);
TreeNode treeNode = invertTree(binaryTree);
System.out.println(treeNode);
}
}