Binary Tree

Question 1

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Answer 1

class Solution {

List<List<Integer>> output = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {

   if (root == null) return output;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);

    int level =0;
    while(!q.isEmpty()){
        int qSize= q.size();
       output.add(new ArrayList<>());

        for(int i=0;i<qSize;i++){
            TreeNode curr = q.poll();
            output.get(level).add(curr.val);

            if(curr.left != null) q.add(curr.left);
            if(curr.right != null) q.add(curr.right);

        }
        level++;
    }

    return output;

    
} }

Question 2

606. Construct String from Binary Tree
     Easy

Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.

Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

Input: root = [1,2,3,4]
Output: “1(2(4))(3)”
Explanation: Originally, it needs to be “1(2(4)())(3()())”, but you need to omit all the unnecessary

Answer 2

/**
* 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 “”;
}

    // Step 1: Start with an empty result string
    StringBuilder result = new StringBuilder();

    // Step 2: Perform preorder traversal
    preorderTraversal(root, result);

    // Step 3: Return the final result string
    return result.toString();

}

private void preorderTraversal(TreeNode node, StringBuilder result) {
    if (node == null) {
        return;
    }

    // Step 4: Append the current node's value to the result
    result.append(node.val);

    // Step 5: Check if the current node has a left child or a right child
    if (node.left != null || node.right != null) {

        // Step 6: If there is a left child, add empty parentheses for it
        result.append("(");
        preorderTraversal(node.left, result);
        result.append(")");
    }

    // Step 7: If there is a right child, process it similarly
    if (node.right != null) {
        result.append("(");
        preorderTraversal(node.right, result);
        result.append(")");
    }

    // Step 8: The recursion will handle all the child nodes
} }