前言：

二叉樹刷題是有固定思維的，請移步

README】二叉樹刷題框架

根據二叉樹創(chuàng)建字符串

題目

點擊跳轉：LeetCode

遞歸解法

這道題其實考察到的是二叉樹的括號表示法，括號表示法依靠括號的劃分來區(qū)分左子樹和右子樹。整體思路不難，也即使遞歸創(chuàng)建：首先字符串中加入結點的值，然后遍歷左子樹和右子樹，在遍歷每棵子樹的時候首先創(chuàng)建(，然后遞歸，接著遞歸完成之后再創(chuàng)建)，對于空結點則表示為（）

也就是如果不要去管題目的其它限制，可以寫出這種情況下遞歸代碼

class Solution { public:string tree2str(TreeNode* root) {string ret;if(root=nullptr)return ret;ret+=to_string(root-val);ret+='(';//遍歷子樹先加左括號ret+=tree2str(root->left);//遞歸ret+=')';//遍歷完成之后再加右括號ret+='(';ret+=tree2str(root->right);ret+=')';} };

這樣創(chuàng)建出的字符串是不滿足題意的，題目要求的是對于可以省略的括號應該省略。比如下圖中結點3由于沒有左右子樹，所以它的空結點就不創(chuàng)建括號，還有結點2它只有左子樹沒有右子樹，但是右子樹寫不寫括號不影響對應，因此可以不寫它右子樹的括號

但是有些括號不能省略，比如下圖中，結點2沒有左子樹但是擁有右子樹，如果此時省略了結點2的左子樹的括號，那么在括號表示法中就無法區(qū)分4到底是左子樹還是右子樹了
所以綜上我們可以寫出如下代碼

class Solution { public:string tree2str(TreeNode* root) {string ret;if(root==nullptr){return ret;}ret+=to_string(root->val);if(root->left==nullptr && root->right==nullptr){return ret;}ret+='(';ret+=tree2str(root->left);ret+=')';if(root->right!=nullptr){ret+='(';ret+=tree2str(root->right);ret+=')';}return ret;} };

如果不滿足 if(root->left==nullptr && root->right==nullptr)，指的就是就是此時 root->left==nullptr 但是root->right!=nulltptr，這種情況下正好就符合我們的邏輯，左子樹遞歸進去創(chuàng)建括號，右子樹進入if判斷也創(chuàng)建括號，以此就正確區(qū)分了左右子樹

優(yōu)化

從剛才代碼的提交結構中大家可以看到，時間以及空間效率都及其低下，其實這也是遞歸的通病，遞歸的思路很簡單。我們在上面的代碼中使用的是string，string用的不好會導致大量的深拷貝，因此會嚴重影響效率。
解決方法就是新建一個沒有返回值的遞歸函數(shù)_tree2str，在主函數(shù)中建立一個string，通過引用傳參即可

class Solution { public:void _tree2str(TreeNode* root,string& ret){if(root==nullptr)return;ret+=to_string(root->val);if(root->left==nullptr && root->right==nullptr)return;ret+='(';_tree2str(root->left,ret);ret+=')';if(root->right!=nullptr){ret+='(';_tree2str(root->right,ret);ret+=')';} }string tree2str(TreeNode* root) {string ret;_tree2str(root,ret);return ret;} };

可以發(fā)現(xiàn)，這樣寫代碼的效率得到了很大的提高

總結

以上是生活随笔為你收集整理的二叉树经典题之根据二叉树创建字符串（二叉树的括号表示法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。