536._Construct_Binary_Tree_from_String.md

536. Construct Binary Tree from String

难度: 中等

刷题内容

原题连接

• https://leetcode.com/problems/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:
There will only be '(', ')', '-' and '0' ~ '9' in the input string.
An empty tree is represented by "" instead of "()".

解题方案

思路 1

递归，每次先找到左子树，然后判断有无右子树，继续下去

class Solution(object):
    def str2tree(self, s):
        """
        :type s: str
        :rtype: TreeNode
        """
        if not s or len(s) == 0:
            return None
        if '(' not in s:
            return TreeNode(int(s))
        
        def paren_pair_idx(s):   
            paren_count = 0
            for i in range(len(s)):
                if s[i] == '(':
                    paren_count += 1
                elif s[i] == ')':
                    paren_count -= 1
                if paren_count == 0 and i > s.find('('):
                    return (s.find('('), i)
                
        root = TreeNode(int(s[:s.find('(')]))
        (paren_left, paren_right) = paren_pair_idx(s)
        root.left = self.str2tree(s[paren_left+1: paren_right])
        if paren_right < len(s) - 1:
            root.right = self.str2tree(s[paren_right+2:-1])  
        else:
            root.right = None
        return root