操作给定的二叉树,将其变换为源二叉树的镜像。
数据范围:二叉树的节点数 , 二叉树每个节点的值
要求: 空间复杂度 。本题也有原地操作,即空间复杂度 的解法,时间复杂度
比如:
源二叉树
镜像二叉树
struct TreeNode* Mirror(struct TreeNode* pRoot ) { struct TreeNode *LeftTreeNode, *RightTreeNode; if(pRoot==NULL) return NULL; LeftTreeNode = Mirror(pRoot->left); RightTreeNode = Mirror(pRoot->right); pRoot->right = LeftTreeNode; pRoot->left = RightTreeNode; return pRoot; }
struct TreeNode* Mirror(struct TreeNode* pRoot ) { // write code here //判断结点是否为空 if(!pRoot) { return NULL; } //交换左右子结点 struct TreeNode*tmp=NULL; tmp=pRoot->left; pRoot->left=pRoot->right; pRoot->right=tmp; //递归左右子树 Mirror(pRoot->left); Mirror(pRoot->right); //返回交换后的根节点 return pRoot; }
左右根子树互换即可,控件复杂度O(1),时间复杂度O(n)
struct TreeNode* Mirror(struct TreeNode* pRoot ) { // write code here if(pRoot==NULL) return NULL; struct TreeNode* tmp=NULL; tmp = pRoot->left; pRoot->left=pRoot->right; pRoot->right=tmp; if(pRoot->left!=NULL) Mirror(pRoot->left); if(pRoot->right!=NULL) Mirror(pRoot->right); return pRoot; }
struct TreeNode* Mirror(struct TreeNode* pRoot ) { // write code here if(pRoot == NULL) return pRoot; struct TreeNode* tmp = NULL; tmp = pRoot->left; pRoot->left = pRoot->right; pRoot->right = tmp; Mirror(pRoot->left); Mirror(pRoot->right); return pRoot; }