五一快乐老铁们,祝大家假期愉快~
然后说个事,以后可能会减少算法题的文章了,因为我对于算法也没有很深的理解,只是和大家分享一下我刷题的过程,所以可能对大家的帮助不大。
一周两更Android系列肯定不会变,然后剩下的一篇我会慢慢尝试新的内容形式,再想想看吧。
今天的算法题目是 二叉树的镜像。
请完成一个函数,输入一个二叉树,该函数输出它的镜像。
例如输入:
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出:
4
/ \
7 2
/ \ / \
9 6 3 1
示例 1:输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1]
限制:0 <= 节点个数 <= 1000
登登,其实这道题的精髓就在于每个子树的左右节点都进行了替换,就完成了一个镜像。所以我们可以通过递归的方式,交换每个左右子节点。
当节点为null,返回null,否则就返回传进来的节点。
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
//继续处理下面的节点
TreeNode leftRoot = mirrorTree(root.right);
TreeNode rightRoot = mirrorTree(root.left);
//交换左右节点
root.left = leftRoot;
root.right = rightRoot;
return root;
}
}
时间复杂度:O(n) 空间复杂度:O(n)。(递归使用栈空间)
利用集合来遍历树的每个节点,然后将每个节点的左右节点交换,一直到所有节点都完成即可。
这里用栈的方式进行处理:
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
//根节点入栈
Stack<TreeNode> stack = new Stack<>() {{ add(root); }};
//遍历每个节点
while(!stack.isEmpty()) {
//出栈一个节点
TreeNode node = stack.pop();
//添加左右子节点
if(node.left != null) stack.add(node.left);
if(node.right != null) stack.add(node.right);
//交换左右节点
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
}
return root;
}
时间复杂度:O(n) 空间复杂度:O(n)
https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof