FilesExpand file tree

 master

/

ConstructBinaryTreeFromString536.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

69 lines (64 loc) · 1.87 KB

 master

/

ConstructBinaryTreeFromString536.java

Copy path

Top

File metadata and controls

• Code
• Blame

69 lines (64 loc) · 1.87 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

/**

* 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 "()".

*/

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

public class ConstructBinaryTreeFromString536 {

public TreeNode str2tree(String s) {

if (s == null || s.length() == 0) return null;

return str2tree(s.toCharArray(), 0, s.length()-1);

}

public TreeNode str2tree(char[] chars, int i, int j) {

if (i > j) return null;

int len = 0;

while (i+len <= j && chars[i+len] != '(' && chars[i+len] != ')') {

len++;

}

TreeNode root = new TreeNode(Integer.parseInt(new String(chars, i, len)));

if (i + len - 1 == j) return root;

int m = i + len;

int count = 0;

while (m <= j) {

if (chars[m] == '(') {

count++;

} else if (chars[m] == ')') {

count--;

}

m++;

if (count == 0) break;

}

root.left = str2tree(chars, i+len+1, m-2);

root.right = str2tree(chars, m+1, j-1);

return root;

}

}