leetcode226.翻转二叉树
Question
翻转一棵二叉树。
示例：
输入：
输出：
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/invert-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
Answer
法一：前序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public static TreeNode invertTree1(TreeNode root) {
if(root == null) {
//递归边界
return null;
}
//swap
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left); //左子树内部交换
invertTree(root.right); //右子树内部交换
return root;
}
法二：中序遍历
注意中序遍历根结点翻转后，左右子树已经交换过，原本invertTree(root.right)要改成invertTree(root.left)
public static TreeNode invertTree2(TreeNode root) {
if(root == null) {
//递归边界
return null;
}
invertTree(root.left);
//swap
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
return root;
}
法三：后序遍历
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
invertTree(root.left);
invertTree(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
return root;
}
Attention
写一个二叉树工具类实现创建二叉树，层序遍历
创建二叉树时
输入是先根输入：4 2 1 0 0 3 0 0 7 6 0 0 9 0 0
翻转后层序遍历输出应该是：4 7 2 9 6 3 1
package pid226;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Solution {
public static TreeNode invertTree(TreeNode root) {
if(root == null) {
//递归边界
return null;
}
//swap
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left); //左子树内部交换
invertTree(root.right); //右子树内部交换
return root;
}
public static TreeNode createBiTree(TreeNode root) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
if(num == 0) {
return null;
}else {
root.val = num;
root.left = createBiTree(new TreeNode(0));
root.right = createBiTree(new TreeNode(0));
return root;
}
}
public static void levelTraverse(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()) {
TreeNode treenode = queue.poll();
System.out.println(treenode.val);
if(treenode.left != null) {
queue.offer(treenode.left);
}
if(treenode.right != null) {
queue.offer(treenode.right);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode root = new TreeNode();
root = createBiTree(root);
invertTree(root);
levelTraverse(root);
}
}
