Simple Java solution beats 60% of submissions


  • 0
    D
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public String tree2str(TreeNode t) {
            
            //variable to store the answer
            StringBuffer answer=new StringBuffer();
            
            //if root is null, return answer
            if(t==null)
                return answer.toString();
                
            //call recursive function to form the string from Binary Tree
            preorderTraversal(t,answer);
            
            //to simplify string and omit unnecessary parantheses
            /*to find the start and end indices of unnecessary parantheses and delete the substring from the solution*/
            int index=-1;
            boolean open=false;
            boolean emptyPair=false;
            int numOpen=0;
            int numClose=0;
            
            int i=0;
            
            //iterate the length of the string
            while(i<answer.length())
            {
                 
                //Case 1: if char is (, if open is not set,mark current index as start of substring to be deleted and increment number of (
                if(answer.charAt(i)=='(')
                {
                    if(!open)
                    {
                        index=i;
                        open=true;
                    }
                    
                    numOpen++;
                }
                
                /*Case 2:if character is ),if an empty parantheses is found, open parantheses is true and number of ( is equal to number of ),
                delete the substring and reset all variables
                If only open is set, then set emptyPair and increment number of )*/
                else if(answer.charAt(i)==')')
                {
                    if(open && emptyPair && numOpen==numClose)
                    {
                        answer.delete(index,i);
                        open=false;
                        emptyPair=false;
                        numOpen=0;
                        numClose=0;
                        i=index+1;
                        continue;
                    }
                    
                    else if(open)
                    {
                        emptyPair=true;
                        numClose++;
                    }
                }
                
                //Case 3:if current chars are numbers just reset everything and carry on
                else
                {
                    open=false;
                    emptyPair=false;
                    numOpen=0;
                    numClose=0;
                }
                
                //increment index
                i++;
            }
            
            
            //Required to omit unnecessary parantheses at the end of the string
            if(open && emptyPair && numOpen==numClose)
            {
                answer.delete(index,i);
            }
            
            
            //return solution
            return answer.toString();
        }
        
        public void preorderTraversal(TreeNode root,StringBuffer answer)
        {
            //Base case: if root is null return
            if(root==null)
                return;
            //General case: if root is present
            // append the root to the string and traverse left and right subtrees
            else    
            {
                answer.append(Integer.toString(root.val));
                answer.append("(");
                preorderTraversal(root.left,answer);
                answer.append(")");
                answer.append("(");
                preorderTraversal(root.right,answer);
                answer.append(")");
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.