博客

题目：

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

struct BinaryTreeNode{
	int m_nValue;
	BinaryTreeNode* m_pLeft;
	BinaryTreeNode* m_pRight;
}

首先理解什么叫二叉树的镜像。我们都知道镜子具有左右相反的功能。故二叉树的镜像树是除根结点以外，其他结点都有顺序的左右交换了顺序。比如上面的图中所示：根结点8没有变换位置，可以根结点的左右结点发生了位置交换。接着以6、10为根结点子树的叶子结点也交换了位置。故我们求一颗镜像树的过程为：我们先前序遍历这颗树的每个结点，如果遍历到的结点有子结点，我们就交换它的两个子结点。当交换完所有非叶子结点的左右子结点之后，我们就得到了一颗树的镜像树。

用递归的代码实现：

public class BinaryTreeNode {

	public int data; 
	public BinaryTreeNode left;
	public BinaryTreeNode right;
	public BinaryTreeNode(int data) {
		this.data = data;
	}
	@Override
	public String toString() {
		return "BinaryTreeNode [data=" + data + ", left=" + left + ", right=" + right
				+ "]";
	}

}

public void mirrorRecursively(BinaryTreeNode pNode){
	if(pNode == null){ //没有树直接返回
		return;
	}
	if(pNode.left == null && pNode.right == null){ //如果左右结点为空，也直接返回
		return;
	}
	BinaryTreeNode pTemp = pNode.left; //交换树的左右结点
	pNode.left = pNode.right;
	pNode.right = pTemp;
	if(pNode.left!=null){ //如果左结点不为空，继续
		mirrorRecursively(pNode.left);
	}
	if(pNode.right != null){ //如果右结点不为空，继续
		mirrorRecursively(pNode.right);
	}
}

用循环借助于栈实现代码：

public void mirrorRecursively1(BinaryTreeNode pNode){
	if(pNode == null){
		return ;
	}
	Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
	stack.push(pNode);
	while(!stack.isEmpty()){
		BinaryTreeNode treeNode = stack.pop();
		if(treeNode.left!=null || treeNode.right!=null){
			BinaryTreeNode tempNode = treeNode.left;
			treeNode.left = treeNode.right;
			treeNode.right = tempNode;
		}
		if(treeNode.left!=null){
			stack.push(treeNode.left);
		}
		if(treeNode.right!=null){
			stack.push(treeNode.right);
		}
	}
}

小结：

考查对二叉树的理解。这道题的本质是用树的遍历算法来解决问题。