# Leetcode 536. Construct Binary Tree from String

You need to construct a binary tree from a string consisting of parenthesis and integers.

The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root’s value and a pair of parenthesis contains a child binary tree with the same structure.

You always start to construct the left child node of the parent first if it exists.

1 2 3 4 5 6 7 8 9 |
Example: Input: "4(2(3)(1))(6(5))" Output: return the tree root node representing the following tree: 4 / \ 2 6 / \ / 3 1 5 |

Note:

There will only be ‘(‘, ‘)’, ‘-‘ and ‘0’ ~ ‘9’ in the input string.

An empty tree is represented by “” instead of “()”.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
/** * 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) { int i = 0; return dfs(s, i); } int get_next_num(string &s, int &i) { int start = i; while (i != (int)s.size() && s[i] != '(' && s[i] != ')') i++; return stoi(s.substr(start, i - start)); } /* 0123456789 4(2(3)(1))(6(5)) 4(2)(3) */ TreeNode *dfs(string &s, int &i) { //base case int size = s.size(); if (i >= size || s[i] == ')') return NULL; if (s[i] == '(') i++; int num = get_next_num(s, i); TreeNode *root = new TreeNode(num); TreeNode *left = dfs(s, i); TreeNode *right = dfs(s, i); root->left = left; root->right = right; if (s[i] == ')') i++; return root; } }; |

` `

# Why google will not hire you

# 像大佬一样

Nothing in this world can take the place of persistence. Talent will not; nothing is more common than unsuccessful men with talent. Genius will not; unrewarded genius is almost a proverb. Education will not; the world is full of educated derelicts. Persistence and determination alone are omnipotent. The slogan Press On! has solved and always will solve the problems of the human race

# AI Engineering: Senior Machine Learning Engineer

# [转]我在美国给7岁儿子恶补数学 竟遭美国老师狠批

# Contributors to MariaDB 10.3.10

Happy to be one of the contributors.

# Spencer’s first comics

# ceph QoS

# ceph client

CEPH CLIENT ARCHITECTURE exclusive-lock, object-map