[LeetCode]Construct Binary Tree from String

很直观的递归题，每次找到左子树对应的括号和右子树对应的括号然后递归地构建树即可，空间复杂度O(d)，d为树的深度。时间复杂度O(n)。代码如下：

	/**
	* 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* str2tree(string s) {
	s = "(" + s + ")";
	int len = s.size();
	return s2T(s, 0, len - 1);
	}
	private:
	TreeNode* s2T(string s, int lo, int hi)
	{
	if(lo + 1 > hi - 1)return nullptr;
	TreeNode* node = nullptr;
	int num = 0, i = lo + 1;
	bool isNeg = s[i] == '-'? true: false;
	if(isNeg)++i;
	while(i < hi && isdigit(s[i]))
	num = num * 10 + (s[i++] - '0');
	node = new TreeNode(isNeg? -num: num);
	if(i == hi)return node;//leaf node
	int count = 0, j = i;
	while(j <= hi)
	{
	if(s[j] == '(')++count;
	else if(s[j] == ')') --count;
	if(!count)break;
	++j;
	}
	node->left = s2T(s, i, j);
	node->right = s2T(s, j + 1, hi - 1);
	return node;
	}
	};

view raw Construct Binary Tree from String.cpp hosted with ❤ by GitHub