_606. Construct String from Binary Tree.md

606. Construct String from Binary Tree

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : August 04, 2024

Last updated : August 04, 2024

---

Related Topics : String, Tree, Depth-First Search, Binary Tree

Acceptance Rate : 69.89 %

---

Solutions

• m606 v2 String Builder.java
• m606.java
• m606.py

Java

m606 v2 String Builder.java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public String tree2str(TreeNode root) {
        return helper(root, new StringBuilder()).toString();
    }

    public StringBuilder helper(TreeNode curr, StringBuilder sb) {
        sb.append(curr.val);

        if (curr.left != null) {
            sb.append("(");
            helper(curr.left, sb);
            sb.append(")");
        } else if (curr.right != null) {
            sb.append("()");
        }
        if (curr.right != null) {
            sb.append("(");
            helper(curr.right, sb);
            sb.append(")");
        }
        return sb;
    }
}

m606.java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public String tree2str(TreeNode root) {
        if (root == null)
            return "";
        if (root.left == null && root.right == null)
            return "" + root.val;

        return root.val
                + "(" + tree2str(root.left) + ")"
                + (root.right != null ? "(" + tree2str(root.right) + ")" : ""); 
    }
}

Python

m606.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def tree2str(self, root: Optional[TreeNode]) -> str:
        if not root :
            return ''
        if not root.left and not root.right :
            return str(root.val)

        output = [str(root.val)]
        if root.left :
            output.extend(['(', self.tree2str(root.left), ')'])
        else :
            output.append('()')
        if root.right :
            output.extend(['(', self.tree2str(root.right), ')'])

        return ''.join(output)