【算法练习六】二叉树反转镜像

二叉树的镜像就是二叉树对称的二叉树,比如
原二叉树
镜像之后
这里写图片描述
就是交换每一非叶子节点的左子树指针和右子树指针
1:递归,如果节点为空,返回,否则交换左右孩子指针;递归镜像节点的左子树,右子树;
2:非递归:交换每一非叶子节点的左子树指针和右子树指针 ,利用队列,根节点先入队;交换队列第一个节点的左右孩子之针,然后把第一个节点的左右孩子入队,然后pop();直到队列为空;即遍历完毕;


递归写法

// Recursion
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (!root) return NULL;
TreeNode *tmp = root->left;
root->left = invertTree(root->right);
root->right = invertTree(tmp);
return root;
}
};

非递归写法

// Non-Recursion
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (!root) return NULL;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode *node = q.front(); q.pop();
TreeNode *tmp = node->left;
node->left = node->right;
node->right = tmp;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
return root;
}
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注