Extremely fast tree traversal solution


  • 0
    L

    We pass our StringBuilder object through the recursive chain, and check whether or not we're at the first recursive iteration. We also check if the node's right value is nil before we dive into another recursive iteration to the left leaf, so we know whether or not we should be showing a () in the case that it is null.

        public String tree2str(TreeNode t) {
            return dfs(t, new StringBuilder(), true, false).toString();
        }
    
        private StringBuilder dfs(TreeNode treeNode, StringBuilder stringBuilder, boolean first, boolean isLeft) {
            if (treeNode != null) {
                if (!first) {
                    stringBuilder.append("(");
                }
                stringBuilder.append(treeNode.val);
                boolean leftOk = false;
                if (treeNode.right != null){
                    leftOk = true;
                }
                stringBuilder = dfs(treeNode.left, stringBuilder, false, leftOk);
                stringBuilder = dfs(treeNode.right, stringBuilder, false, leftOk);
                if (!first) {
                    stringBuilder.append(")");
                }
            } else if (isLeft){
                stringBuilder.append("()");
            }
            return stringBuilder;
        }
    

Log in to reply
 

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