Java Solution, Tree Traversal


  • 16
    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 + ")";
        }
    }
    

  • 4

    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.


  • 0

    @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?


  • 4

    @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.


  • 0

    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
        }
    }
    

Log in to reply
 

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