LeetCode 536. 从字符串生成二叉树（递归）

Michael阿明

发布于 2021-02-19 10:15:32

1.2K0

发布于 2021-02-19 10:15:32

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

你需要从一个包括括号和整数的字符串构建一棵二叉树。

输入的字符串代表一棵二叉树。它包括整数和随后的0，1或2对括号。整数代表根的值，一对括号内表示同样结构的子树。

若存在左子结点，则从左子结点开始构建。（题目意思：先有左节点）

示例:
输入: "4(2(3)(1))(6(5))"
输出: 返回代表下列二叉树的根节点:

       4
     /   \
    2     6
   / \   / 
  3   1 5   
 

注意:
输入字符串中只包含 '(', ')', '-' 和 '0' ~ '9' 
空树由 "" 而非"()"表示。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/construct-binary-tree-from-string 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

class Solution {
	int i = 0;
public:
    TreeNode* str2tree(string s) {
    	if(s == "") return NULL;
    	return buildTree(s);
    }
    TreeNode* buildTree(string &s)
    {
    	if(i == s.size())
    		return NULL;
        int val = 0, neg = 1;
        if(s[i] == '-')
        {
            neg = -1;//负数
            i++;
        }
        while(isdigit(s[i]))
            val = val*10 + neg*(s[i++]-'0');//计算值
    	TreeNode* root = new TreeNode(val);
    	if(i < s.size() && s[i] == '(' && !root->left)
    	{
    		i++;
    		root->left = buildTree(s);
    	}
    	if(i < s.size() && s[i] == '(' && !root->right)
    	{
    		i++;
    		root->right = buildTree(s);
    	}
        i++;// 跳过 )
    	return root;
    }
};

60 ms 26.4 MB

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/07/23 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树