Java Solution, Tree Traversal


  • 19
    public class Solution {
        public String tree2str(TreeNode t) {
            if (t == null) return "";
            
            String result = t.val + "";
            
            String left = tree2str(t.left);
            String right = tree2str(t.right);
            
            if (left == "" && right == "") return result;
            if (left == "") return result + "()" + "(" + right + ")";
            if (right == "") return result + "(" + left + ")";
            return result + "(" + left + ")" + "(" + right + ")";
        }
    }
    

  • 5

    Just a bit different.

    public String tree2str(TreeNode t) {
        if(t == null) return "";
        String left = tree2str(t.left);
        String right = tree2str(t.right);
    
        if(left == "" && right == "") return  t.val + "";
    
        return t.val + "(" + left  + ")" + (right == "" ? "" : "(" + right + ")");  
    }
    

    EDIT : Changed from (left == "" ? "" : left) to left.


  • 0

    @shawngao said in Java Solution, Tree Traversal:

    == ""
    

    Might be good to explain why that is safe, why you don't need to use the equals method.


  • 1

    @jaqenhgar said in Java Solution, Tree Traversal:

    (left == "" ? "" : left)
    

    That's equivalent to just left, isn't it?


  • 0
    S

    Just curious: will StringBuilder be more efficient than string concatenation is?


  • 5

    @StefanPochmann said in Java Solution, Tree Traversal:

    Might be good to explain why that is safe, why you don't need to use the equals method.

    That's a good question. As you know, in Java, == compares reference and equals compares value. We should always use equals to be safe.

    Why == works here is because (I think) Java compiler is clever enough that if multiple variables are assigned the same String value, they point to the same static String instance. Please see the following code snippet:

            String a = "";
            String b = "";
            String c = new String("");
            String d = new StringBuilder(a).toString();
            String[] e = new String[1];
            e[0] = "";
            String[] f = {""};
    
            System.out.println(a == "");
            System.out.println(a == b);
            System.out.println(a == c);
            System.out.println(a == d);
            System.out.println(a == e[0]);
            System.out.println(a == f[0]);
    

    The output is:

    true
    true
    false
    false
    true
    true
    

    Only c and d point to a different String instance. Others all point to the same one.

    But, as I said above, it is always safe to use equals.


  • 0

    @StefanPochmann That's right. :| - Corrected.


  • 0

    @shawngao Just to add, a.intern() == c.intern() will be true.
    String intern() will refer to the strings in the String Pool, regardless of how the object was created.

    But as long as we know we didn't create the object using "new", we should be okay to use ==.


  • 2
    D

    @szyyn95 String concat create a new string every time whereas Stringbuilder doesn't. That is why it's better.


  • 0
    H
    string tree2str(TreeNode* t) {
            if(t == NULL) return "";
            string val = to_string(t->val);
            string left = tree2str(t->left);
            string right = tree2str(t->right);
            
            if(left == "" && right == "") return val;
            if(left == "") return val + "()" + "(" + right + ")";
            if(right == "") return val + "(" + left + ")";
            return val + "(" + left + ")" + "(" + right + ")"; 
        }

  • 0
    D

    Use StringBuilder:

    public class Solution {
        public String tree2str(TreeNode t) 
        {
            return dfs(t).toString();
        }
        
        private StringBuilder dfs(TreeNode n)
        {
            if (n == null) { return new StringBuilder(); }
            
            // go right
            StringBuilder r = dfs(n.right);
            // go left
            StringBuilder l = dfs(n.left);
            
            if (r.length() != 0)
            {
                r.insert(0, "(").append(")");
            }
            
            if (l.length() != 0)
            {
                l.insert(0, "(").append(")");
            }
            
            if (l.length() == 0 && r.length() != 0)
            {
                l.append("()");
            }
            
            // combine
            return l.append(r).insert(0, n.val);
        }
    }
    

  • 0
    H

    same idea with StringBuilder.

            if(t==null) return "";
            StringBuilder sb=new StringBuilder();
            sb.append(t.val);
            if(t.left!=null) sb.append("("+tree2str(t.left)+")");
            else if(t.right!=null) sb.append("()");
            if(t.right!=null) sb.append("("+tree2str(t.right)+")");        
            return sb.toString();
    

  • 0

    @shawngao

    Yes. Not sure about if it's same in Java, but in a word, Equals() compares values, while == compares object references.


  • 1

    An iterative solution:

        public string Tree2str(TreeNode t) {
            if(t == null)
                return "";
            
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.Push(t);
            
            HashSet<TreeNode> visited = new HashSet<TreeNode>();
            StringBuilder res =  new StringBuilder();
            
            while(stack.Any())
            {
                t = stack.Peek();
                if(visited.Contains(t)) //Vistied before, pop and put a close ) into res
                {
                    stack.Pop();
                    res.Append(')');
                }
                else //Not visited before
                {
                    visited.Add(t);
                    res.Append('(').Append(t.val);
                    //If left is null, right is not null.need to put a pair of brakcet
                    if(t.left == null && t.right != null)  
                        res.Append("()");
    
                    //Push its children into stack
                    if(t.right != null)                    //Case: right not null
                        stack.Push(t.right);
    
                    if(t.left != null)                      //Case: left not null
                        stack.Push(t.left);
                }
            }
            return res.ToString(1, res.Length - 2);        //Trim the most outer brackets
        }
    }
    

  • 0

    Share my DFS backtracking tree traversal solution to avoid string concatenation (cause it would be O(k) time complexity). Add root.val at preOrder position and delete parenthesis at postOrder position. Thanks~

    public class Solution {
        public String tree2str(TreeNode t) {
            StringBuilder sb = new StringBuilder();
            dfs(t, sb);
    
            return String.valueOf(sb);
        }
    
        private void dfs(TreeNode root, StringBuilder sb) {
            //base case
            if (root == null) {
                return;
            }
            //preOrder position
            sb.append(root.val);
    
            sb.append("(");
            dfs(root.left, sb);
            sb.append(")");
    
            sb.append("(");
            dfs(root.right, sb);
            sb.append(")");
    
            //postOrder position
            if (root.right == null) {
                sb.delete(sb.length() - 2, sb.length());
            }
            if (root.right == null && root.left == null) {
                sb.delete(sb.length() - 2, sb.length());
            }
        }
    }
    

  • 0

    Another Approach.

    public String tree2str(TreeNode t) {
         if (t == null) return "";
         String left = tree2str (t.left), right = tree2str (t.right);
         if (left.length () == 0 && right.length () == 0) return String.valueOf (t.val);
         else return t.val + "(" + left + ")" + (right.length () > 0 ? "(" + right + ")" : "");
    }
    

  • 0
    T
    public String tree2str(TreeNode root) {
        return serialize(root, new StringBuilder()).toString();
    }
    private StringBuilder serialize(TreeNode node, StringBuilder sb) {
        if (node != null) {   
            sb.append(node.val);
            if(node.left!=null) {
                sb.append('(');
                serialize(node.left, sb);
                sb.append(')');
                if(node.right!=null){
                    sb.append('(');
                    serialize(node.right, sb);
                    sb.append(')');
                }
            }            
            else if(node.right!=null) {
                sb.append('(');
                sb.append(')');
                sb.append('(');
                serialize(node.right, sb);
                sb.append(')');
            }
        }
        return sb;
    }

  • 0

    @shawngao said in Java Solution, Tree Traversal:

        String result = t.val + "";
    

    Nice solution! I'm surprised to learn that we could assemble a Java String by int and String.

    Reference StackOverflow link: https://stackoverflow.com/q/14782804/3697757


Log in to reply
 

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