536 Construct Binary Tree from String

536. Construct Binary Tree from String
1. Question
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 theleftchild node of the parent first if it exists.
Example:
1
Input: "4(2(3)(1))(6(5))"
2
​
3
Output: return the tree root node representing the following tree:
4
​
5
       4
6
     /   \
7
    2     6
8
   / \   / 
9
  3   1 5
Copied!
Note:
1.There will only be'(',')','-'and'0'~'9'in the input string.
2.An empty tree is represented by""instead of"()".
2. Implementation
(1) Recursion
1
class Solution {
2
    int i;
3
    public TreeNode str2tree(String s) {
4
        i = 0;
5
        return buildTree(s);
6
    }
7
​
8
    public TreeNode buildTree(String s) {
9
        StringBuilder num = new StringBuilder();
10
​
11
        while (i < s.length() && (s.charAt(i) == '-' || Character.isDigit(s.charAt(i)))) {
12
            num.append(s.charAt(i));
13
            i++;
14
        }
15
​
16
        if (num.length() == 0) {
17
            return null;
18
        }
19
​
20
        TreeNode root = new TreeNode(Integer.parseInt(num.toString()));
21
​
22
        // Left SubTree
23
        if (i < s.length() && s.charAt(i) == '(') {
24
            // Skip '('
25
            ++i;
26
            root.left = buildTree(s);
27
            // Skip ')'
28
            ++i;
29
        }
30
​
31
        // Right SubTree
32
        if (i < s.length() && s.charAt(i) == '(') {
33
            ++i;
34
            root.right = buildTree(s);
35
            ++i;
36
        }
37
        return root;
38
    }
39
}
Copied!
(2) Iteration
1
class Solution {
2
    public TreeNode str2tree(String s) {
3
        if (s == null || s.length() == 0) {
4
            return null;
5
        }
6
​
7
        Stack<TreeNode> stack = new Stack<>();
8
​
9
        for (int end = 0, start = 0; end < s.length(); end++, start = end) {
10
            char c = s.charAt(end);
11
​
12
            if (c == '(') {
13
                continue;
14
            }
15
            else if (c == ')') {
16
                stack.pop();
17
            }
18
            else {
19
                while (end + 1< s.length() && Character.isDigit(s.charAt(end + 1))) {
20
                    ++end;
21
                }
22
                TreeNode curNode = new TreeNode(Integer.parseInt(s.substring(start, end + 1)));
23
​
24
                if (!stack.isEmpty()) {
25
                    TreeNode parentNode = stack.peek();
26
                    if (parentNode.left != null) {
27
                        parentNode.right = curNode;
28
                    }
29
                    else {
30
                        parentNode.left = curNode;
31
                    }
32
                }
33
                stack.push(curNode);
34
            }
35
        }
36
        return stack.isEmpty() ? null : stack.peek();
37
    }
38
}
Copied!
3. Time & Space Complexity
Recursion: 时间复杂度O(n), 空间复杂度O(n)
Iteration: 时间复杂度O(n), 空间复杂度O(n)

156 Binary Tree Upside Down

543 Diameter of Binary Tree

Last modified 2yr ago

Copy link

Contents

536. Construct Binary Tree from String

1. Question

2. Implementation

3. Time & Space Complexity