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.

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:

  1. There will only be '('')''-' and '0' ~ '9' in the input string.
  2. An empty tree is represented by "" instead of "()".

 

这道题让我们根据一个字符串来创建一个二叉树,其中结点与其左右子树是用括号隔开,每个括号中又是数字后面的跟括号的模式,这种模型就很有递归的感觉,所以我们当然可以使用递归来做。首先我们要做的是先找出根结点值,我们找第一个左括号的位置,如果找不到,说明当前字符串都是数字,直接转化为整型,然后新建结点返回即可。否则的话从当前位置开始遍历,因为当前位置是一个左括号,我们的目标是找到与之对应的右括号的位置,但是由于中间还会遇到左右括号,所以我们需要用一个变量 cnt 来记录左括号的个数,如果遇到左括号,cnt 自增1,如果遇到右括号,cnt 自减1,这样当某个时刻 cnt 为0的时候,我们就确定了一个完整的子树的位置,那么问题来了,这个子树到底是左子树还是右子树呢,我们需要一个辅助变量 start,当最开始找到第一个左括号的位置时,将 start 赋值为该位置,那么当 cnt 为0时,如果 start 还是原来的位置,说明这个是左子树,我们对其调用递归函数,注意此时更新 start 的位置,这样就能区分左右子树了,参见代码如下:

 

解法一:

class Solution {
public:
    TreeNode* str2tree(string s) {
        if (s.empty()) return NULL;
        auto found = s.find('(');
        int val = (found == string::npos) ? stoi(s) : stoi(s.substr(0, found));
        TreeNode *cur = new TreeNode(val);
        if (found == string::npos) return cur;
        int start = found, cnt = 0;
        for (int i = start; i < s.size(); ++i) {
            if (s[i] == '(') ++cnt;
            else if (s[i] == ')') --cnt;
            if (cnt == 0 && start == found) {
                cur->left = str2tree(s.substr(start + 1, i - start - 1));
                start = i + 1;
            } else if (cnt == 0) {
                cur->right = str2tree(s.substr(start + 1, i - start - 1));
            }
        }
        return cur;
    }
};

 

下面这种解法使用迭代来做的,借助栈 stack 来实现。遍历字符串s,用变量j记录当前位置i,然后看当前遍历到的字符是什么,如果遇到的是左括号,什么也不做继续遍历;如果遇到的是数字或者负号,那么我们将连续的数字都找出来,然后转为整型并新建结点,此时我们看 stack 中是否有结点,如果有的话,当前结点就是栈顶结点的子结点,如果栈顶结点没有左子结点,那么此结点就是其左子结点,反之则为其右子结点。之后要将此结点压入栈中。如果我们遍历到的是右括号,说明栈顶元素的子结点已经处理完了,将其移除栈,参见代码如下:

 

解法二:

class Solution {
public:
    TreeNode* str2tree(string s) {
        if (s.empty()) return NULL;
        stack<TreeNode*> st;
        for (int i = 0; i < s.size(); ++i) {
            int j = i;
            if (s[i] == ')') st.pop();
            else if ((s[i] >= '0' && s[i] <= '9') || s[i] == '-') {
                while (i + 1 < s.size() && s[i + 1] >= '0' && s[i + 1] <= '9') ++i;
                TreeNode *cur = new TreeNode(stoi(s.substr(j, i - j + 1)));
                if (!st.empty()) {
                    TreeNode *t = st.top();
                    if (!t->left) t->left = cur;
                    else t->right = cur;
                }
                st.push(cur);
            }
        }
        return st.top();
    }
};

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/536

 

类似题目:

Construct String from Binary Tree

 

参考资料:

https://leetcode.com/problems/construct-binary-tree-from-string/

https://leetcode.com/problems/construct-binary-tree-from-string/discuss/100359/Java-stack-solution

https://leetcode.com/problems/construct-binary-tree-from-string/discuss/100355/Java-Recursive-Solution

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation