您现在的位置:首页 > >

二叉树的镜像(先序遍历)

发布时间:

1、题目

2、思路

二叉树有0个节点
二叉树有1个节点
二叉树有多个节点(普通二叉树和只有单侧子节点的二叉树)
二叉树有多个节点的思路:前序遍历二叉树的每个节点,如果遍历到的节点有子节点,则交换该节点的两个子节点。当交换完所有非叶子结点的左右节点之后,即得到二叉树的镜像。



struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
class Solution {
public:
void Mirror(TreeNode *pRoot) {
// 空节点
if(pRoot==nullptr)
return;

// 叶子结点
if(pRoot->left==nullptr&&pRoot->right==nullptr)
return;

// 二叉树有多个节点时,交换当前节点的左右节点
TreeNode* temp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = temp;

// 二叉树的遍历
Mirror(pRoot->left);
Mirror(pRoot->right);
}
};


热文推荐
猜你喜欢
友情链接: