一、前言
本系列文章为《剑指Offer》刷题笔记。
刷题平台:牛客网
书籍下载:共享资源
二、题目
如下图所示:
1、思路
先交换根节点的两个子结点之后,我们注意到值为10、6的结点的子结点仍然保持不变,因此我们还需要交换这两个结点的左右子结点。做完这两次交换之后,我们已经遍历完所有的非叶结点。此时变换之后的树刚好就是原始树的镜像。交换示意图如下所示:
2、代码
C++:
/* 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 == NULL) || (pRoot->left == NULL && pRoot->right == NULL)){ return; } //交换根节点的左右结点 TreeNode *pTemp = pRoot->left; pRoot->left = pRoot->right; pRoot->right = pTemp; //递归左子树 if(pRoot->left){ Mirror(pRoot->left); } //递归右子树 if(pRoot->right){ Mirror(pRoot->right); } } };
Python2.7:
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # 返回镜像树的根节点 def Mirror(self, root): # write code here if (root == None or (root.left == None and root.right == None)): return None tmp = root.left root.left = root.right root.right = tmp if root.left: self.Mirror(root.left) if root.right: self.Mirror(root.right)
来源:
https://cuijiahua.com/blog/2017/12/basis_18.html