二叉树的镜像

1. 题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。 输入描述:

二叉树的镜像定义：源二叉树 
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

2. 思路

• 交换左右节点+先序遍历
• 交换左右节点+层次遍历

3. 实现

3.1. 先序遍历

• java

public class 二叉树的镜像
{
    public void Mirror(TreeNode root)
    {
        //检查参数为空
        if (root == null)
        {
            return;
        }
        //左右节点交换
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        //对左子树做同样的操作
        this.Mirror(root.left);
        //对右子树做同样的操作
        this.Mirror(root.right);
    }
}

• go

//时间复杂度：O(n),n为树节点的个数。每个节点只用遍历一次，所以为O(n)
//空间复杂度：O(n), 每个节点都会在递归栈中存一次
func Mirror3(pRoot *TreeNode) *TreeNode {
	if pRoot == nil {
		return nil
	}
	pRoot.Left, pRoot.Right = pRoot.Right, pRoot.Left
	Mirror(pRoot.Left)
	Mirror(pRoot.Right)

	return pRoot
}

3.2. 层次遍历

• go

//时间复杂度：O(n),n为树节点的个数。每个节点只用遍历一次，所以为O(n)
//空间复杂度：O(n)
func Mirror(pRoot *TreeNode) *TreeNode {
	if pRoot == nil {
		return nil
	}
	//先序遍历使用栈
	stack := make([]*TreeNode, 0)
	stack = append(stack, pRoot)
	for len(stack) > 0 {
		removed := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		removed.Left, removed.Right = removed.Right, removed.Left
		if removed.Left != nil {
			stack = append(stack, removed.Left)
		}
		if removed.Right != nil {
			stack = append(stack, removed.Right)
		}
	}

	return pRoot
}


func Mirror2(pRoot *TreeNode) *TreeNode {
	if pRoot == nil {
		return nil
	}
	//层序遍历使用队列
	queue := make([]*TreeNode, 0)
	queue = append(queue, pRoot)
	for len(queue) > 0 {
		removed := queue[0]
		queue = queue[1:]
		removed.Left, removed.Right = removed.Right, removed.Left
		if removed.Left != nil {
			queue = append(queue, removed.Left)
		}
		if removed.Right != nil {
			queue = append(queue, removed.Right)
		}
	}

	return pRoot
}

4. 参考

• 二叉树的镜像_牛客网
• Invert Binary Tree - LeetCode