C语言重构【606】根据二叉树创建字符串

￡神魔★判官ぃ 2022-12-19 06:14 88阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
    
    空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
    
    示例 1:
    
    输入: 二叉树: [1,2,3,4]
           1
         /   \
        2     3
       /    
      4     
    
    输出: "1(2(4))(3)"
    
    解释: 原本将是“1(2(4)())(3())”，
    在你省略所有不必要的空括号对之后，
    它将是“1(2(4))(3)”。
    示例 2:
    
    输入: 二叉树: [1,2,3,null,4]
           1
         /   \
        2     3
         \  
          4 
    
    输出: "1(2()(4))(3)"
    
    解释: 和第一个示例相似，
    除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。

#### 方案： ####

/** * 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:
        string tree2str(TreeNode* t) { 
            if(t==NULL) return "";
            
            return t2s(t);
        }
        
        string t2s(TreeNode* t) { 
            
            if(t->left==NULL&&t->right==NULL){ 
                return to_string(t->val);
            }
            else{ 
                string left = "()",right="";
                if(t->left!=NULL)left = "("+t2s(t->left)+")";
                if(t->right!=NULL)right = "("+t2s(t->right)+")";
                return to_string(t->val)+left+right;
            }
            
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode