当前位置：首页 > article >正文

LeetCode 606.根据二叉树创建字符串

article 2024/11/10 21:10:36

LeetCode 606.根据二叉树创建字符串

思路🧐：

根据示例发现，当结点左右都为空时可以省略括号，结点仅左为空时，不能省略括号，因为分不清到底是左为空还是右为空，所以我们在解题时需要判断结点的左右情况。

题目要求前序遍历(根左右)，我们可以用to_string将val转为字符传并赋给str，。然后开始走左边，这里要判断一下，如果左和右有一个不为空那么我们就需要加上括号，当走到空或者函数走完时就返回字符串回到上一次递归，开始遍历右边，右边只需要判断是否为空，不为空就进行递归。当遍历完该树后，str就是前序字符串。

代码🔎：

class Solution {
public:
    string tree2str(TreeNode* root) {
        string str;
        if(root == nullptr) //为空就返回字符串
            return str;
        
        str += to_string(root->val); //加上值
        

        if(root->left || root->right) //左子树要两边都不为空才不用写
        {
            str += '(';
            str += tree2str(root->left);
            str += ')';
        }

        if(root->right) //右子树只用判断自己
        {
            str += '(';
            str += tree2str(root->right);
            str += ')';
        }

        return str;
    }
};