数据结构与算法—翻转二叉树
大家好，我是宇哥
题目：226. 翻转二叉树
翻转一棵二叉树。
示例：
输入：
4\2 7\ / \1 3 6 9
输出：
4\7 2\ / \9 6 3 1
解题思路
深度优先和广度优先
深度优先思路
判断根节点，不空加入队列中
递归的交换节点
返回替换后的节点
代码
public TreeNode invertTree(TreeNode root) {if (root == null) return null;// 交换节点TreeNode temp = root.left;root.left = invertTree(root.right);root.right = invertTree(temp);return root;}
复杂度
时间复杂度：O(N)，其中N为二叉树节点数，循环会遍历每一个节点
空间复制度：O(N)，其中N为二叉树的节点数，在二叉树比较平衡的情况下，高度与节点树成对数即Olog(N)。最坏的情况成链O(N)
广度优先思路
判断根节点，不空加入队列中
循环队列数据
左右节点替换
如果左右节点不空，向队列中添加
代码
class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()) {TreeNode node = queue.poll();// 交换TreeNode temp = node.left;node.left = node.right;node.right=temp;// 添加子元素if (node.left!=null){queue.offer(node.left);}if (node.right!=null){queue.offer(node.right);}}return root;}
复杂度
时间复杂度：O(N)，其中N为二叉树节点数，循环会遍历每一个节点
空间复制度：O(N)，其中N为二叉树的节点数，主要是节点放到队列中，队列长度不会超节点数
题：https://leetcode-cn.com/problems/invert-binary-tree
欢迎广大人民群众，快乐三连击：【点赞，在看，分享】 好东西又分享出来