一、题目大意
给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。
示例 1:
输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]
示例 2:
输入:root = [2,1,3]
输出:[2,3,1]
示例 3:
输入:root = []
输出:[]
提示:
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100
二、解题思路
翻转二叉树是树的基本操作之一,可以使用递归和非递归两种方法。递归方法:交换当前左右节点,并直接调用递归即可。非递归方法:跟二叉树的层序遍历一样,需要用queue画辅助,先把根节点排入队列中,然后从队列中取出来,交换其左右节点,如果存在则分别将左右节点再排入队列中,以此类推直到队列中没有节点了
三、解题方法3.1 Java实现-递归
public class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return root; } TreeNode tmp = root.left; root.left = invertTree(root.right); root.right = invertTree(tmp); return root; }}
3.2 Java实现-非递归
public class Solution2 { public TreeNode invertTree(TreeNode root) { if (root == null) { return root; } Deque q = new ArrayDeque(); q.push(root); while (!q.isEmpty()) { TreeNode node = q.pop(); TreeNode tmp = node.left; node.left = node.right; node.right = tmp; if (node.left != null) { q.push(node.left); } if (node.right != null) { q.push(node.right); } } return root; }}
四、总结小记
- 2022/9/29 在你成为领导者之前,成功的全部就是自我的成长;当你成了领导者,成功的全部就变成帮助他人成长。—通用电气CEO 杰克 · 韦尔奇《商业的本质》