题目描述
输入一个二叉树,将它变换为它的镜像。
数据范围
树中节点数量 [0,100]。
样例
输入树:
8
/ \
6 10
/ \ / \
5 7 9 11
[8,6,10,5,7,9,11,null,null,null,null,null,null,null,null]
输出树:
8
/ \
10 6
/ \ / \
11 9 7 5
[8,10,6,11,9,7,5,null,null,null,null,null,null,null,null]
思路阐述及口诀
(二叉树,递归) O(n)
仔细观察原树和镜像之后的树:
原树:
8
/ \
6 10
/ \ / \
5 7 9 11
镜像后的树:
8
/ \
10 6
/ \ / \
11 9 7 5
我们可以发现镜像后的树就是将原树的所有节点的左右儿子互换!
所以我们递归遍历原树的所有节点,将每个节点的左右儿子互换即可。
时间复杂度
原树仅被遍历一次,所以时间复杂度是 O(n)。
算法1:注意树节点的交换
public void mirror(TreeNode root) {
if (root == null) return;
swapR(root);
mirror(root.left);
mirror(root.right);
}
private void swapR(TreeNode cur){
TreeNode t = null;
t = cur.left;
cur.left = cur.right;
cur.right = t;
}
算法2
public:
void mirror(TreeNode* root) {
if (!root) return;
swap(root->left, root->right);
mirror(root->left);
mirror(root->right);
}
算法3
算法4