题解 | #二叉树的镜像#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return TreeNode类
 */
void reverse(struct TreeNode *q)
{
  if (q->left || q->right)
  {
    struct TreeNode *temp;
    temp = q->left;
    q->left = q->right;
    q->right = temp;
  }
}

struct TreeNode *Mirror(struct TreeNode *pRoot)
{
   if(!pRoot)
       return NULL;
  //队列层序遍历记录每一层根节点的位置
  //已有节点不删除
  struct TreeNode  *temp;
  struct TreeNode *que[1500];
  int front = 0, rear = 0;
  que[++rear] = pRoot;
  while (rear != front)
  {
    temp = que[++front];
    if (temp->left)
      que[++rear] = temp->left;
    if (temp->right)
      que[++rear] = temp->right;
  }
  for (int i = front; i >= 1; i--)
    reverse(que[i]);

  return  pRoot;

}

struct TreeNode *Mirror(struct TreeNode *pRoot)
{
  if (!pRoot)
    return NULL;
  //递归
  struct TreeNode *temp;
  temp = pRoot->left;
  pRoot->left = pRoot->right;
  pRoot->right = temp;

  pRoot->left = Mirror(pRoot->left);
  pRoot->right = Mirror(pRoot->right);

  return pRoot;
}