Leetcode-536. Construct Binary Tree from String

前言：为了后续的实习面试，开始疯狂刷题，非常欢迎志同道合的朋友一起交流。因为时间比较紧张，目前的规划是先过一遍，写出能想到的最优算法，第二遍再考虑最优或者较优的方法。如有错误欢迎指正。博主首发，mcf171专栏。这次比赛略无语，没想到前3题都可以用暴力解。

博客链接：mcf171的博客

——————————————————————————————

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. 这个题目耽误了很久，主要是没太想明白这个堆的压入和压出的操作。可惜是最后超时提交，没啥用了。

public class Solution { public TreeNode str2tree(String s) { if(s.length() == 0) return null; Stack<TreeNode> stack = new Stack<TreeNode>(); int start = 0, end = 0; TreeNode root = null,parents = null, node = null; int flag = 1; while(start < s.length()){ if(s.charAt(start) == '('){ stack.push(parents); start ++; }else if(s.charAt(start) == ')'){ parents = stack.pop(); if(parents.left == null) {parents.left = node;node=parents;} else{parents.right = node;node = parents;} start ++; }else if(s.charAt(start) == '-') {flag = -1;start ++;} else{ end = findTheNum(s,start); int val = 0; for(int i = start; i < end; i ++) val = val*10 + (s.charAt(i) - '0'); node = new TreeNode(val * flag); start = end; parents = node; if(root == null) root = node; flag = 1; } } return root; } private int findTheNum(String s, int start){ for(;start<s.length(); start ++) if((s.charAt(start) - '0') * (s.charAt(start) - '9') > 0) break; return start; } }