劍指 Offer 27. 二叉樹(shù)的鏡像

思路一:遞歸

從根節(jié)點(diǎn)開(kāi)始，遞歸的對(duì)樹(shù)進(jìn)行遍歷，并從葉子節(jié)點(diǎn)開(kāi)始翻轉(zhuǎn)，得到鏡像。如果當(dāng)前遍歷到的節(jié)點(diǎn)root的左右兩棵子樹(shù)都已經(jīng)翻轉(zhuǎn)得到了鏡像，那么我們只需要交換兩棵子樹(shù)的位置，即可得到以root為跟節(jié)點(diǎn)的整顆子樹(shù)的鏡像。

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:TreeNode* mirrorTree(TreeNode* root) {//首先確定遞歸的截至條件，當(dāng)為空時(shí)候直接返回結(jié)束遞歸if(root==nullptr) return root;//不為空時(shí)候，先左邊深度往下遞歸尋找，再右邊尋找if(root->left!=nullptr) mirrorTree(root->left);if(root->right!=nullptr) mirrorTree(root->right);//找到最后一層，左右節(jié)點(diǎn)進(jìn)行交換TreeNode* tempNode = root->left;root->left = root->right;root->right = tempNode;//返回交換后的結(jié)果return root;} };

遞歸部分優(yōu)化代碼

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:TreeNode* mirrorTree(TreeNode* root) {//首先確定遞歸的截至條件，當(dāng)為空時(shí)候直接返回結(jié)束遞歸if(root==nullptr) return nullptr;//不為空時(shí)候，先左邊深度往下遞歸尋找，再右邊尋找// if(root->left!=nullptr) mirrorTree(root->left);// if(root->right!=nullptr) mirrorTree(root->right);TreeNode* left = mirrorTree(root->left);TreeNode* right= mirrorTree(root->right);//找到最后一層，左右節(jié)點(diǎn)進(jìn)行交換root->left = right;root->right = left;//返回交換后的結(jié)果return root;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode-剑指 Offer 27. 二叉树的镜像的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。