题目描述

给定一颗二叉树，将其左右对称翻转

思路分析

翻转二叉树，就是将每个节点的左右子树都调换位置，记住是每个节点。只需要能遍历每一个节点就可以了，遍历时调换其左右节点就行。

下面是4种方法

前序遍历翻转

中序遍历翻转

后序遍历翻转

层次遍历翻转

代码

/** * 翻转二叉树 */ public class TreeFanzhuan { class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; TreeNode(int val) { this.val = val; } } //先序翻转 TreeNode invest_pre(TreeNode node) { if (node == null) { return null; } //翻转 TreeNode ls = node.left; node.left = node.right; node.right = ls; invest_pre(node.left); invest_pre(node.right); return node; } //中序翻转 TreeNode invest_in(TreeNode node) { if (node == null) { return null; } //翻转 invest_pre(node.left); TreeNode ls = node.left; node.left = node.right; node.right = ls; /** * 这里是中序遍历不一样的地方 */ invest_pre(node.left); return node; } //后序翻转 TreeNode invest_last(TreeNode node) { if (node == null) { return null; } //翻转 invest_pre(node.left); invest_pre(node.right); TreeNode ls = node.left; node.left = node.right; node.right = ls; return node; } //层次翻转 TreeNode invest_(TreeNode node) { if (node == null) { return null; } //队列 Queue<TreeNode> queue = new LinkedList<>(); queue.add(node); while (!queue.isEmpty()) { //出队 TreeNode poll = queue.poll(); //左右交换 即 翻转(某一个为空,都要交换) TreeNode ls = poll.right; poll.right = poll.left; poll.right = ls; //左不为空,入队 if (poll.left != null) { queue.add(poll.left); } //右不为空,入队 if (poll.right != null) { queue.add(poll.right); } } return node; } }