655. Print Binary Tree

Description

Given the root of a binary tree, construct a 0-indexed m x n string matrix res that represents a formatted layout of the tree. The formatted layout matrix should be constructed using the following rules:

• The height of the tree is height and the number of rows m should be equal to height + 1.

• The number of columns n should be equal to 2height+1 - 1.

• Place the root node in the middle of the top row (more formally, at location res[0][(n-1)/2]).

• For each node that has been placed in the matrix at position res[r][c], place its left child at res[r+1][c-2height-r-1] and its right child at res[r+1][c+2height-r-1].

• Continue this process until all the nodes in the tree have been placed.

• Any empty cells should contain the empty string "".

Return the constructed matrix res.

Constraints

• The number of nodes in the tree is in the range [1, 210].

• -99 <= Node.val <= 99

• The depth of the tree will be in the range [1, 10].

Approach

Links

• Binarysearch

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: root = [1, 2]

Output:

[

["", "1", ""],

["2", "", ""]

]

Example 2

Input: root = [1, 2, 3, null, 4]

Output:

[

["", "", "", "1", "", "", ""],

["", "2", "", "", "", "3", ""],

["", "", "4", "", "", "", ""]

]

Solutions

TreeNode

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

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<List<String>> printTree(TreeNode root) {
        List<List<String>> resultMatrix = new ArrayList<>();
        
        if(root == null) {
            return resultMatrix;
        }
        
        int treeHeight = height(root);
        int treeBase = (1 << treeHeight) - 1;
        
        initMatrix(treeHeight, treeBase, resultMatrix);
        
        setNode(root, 0, 0, treeBase, resultMatrix);
        
        return resultMatrix;
    }
    
    private void setNode(TreeNode root, int row, int low, int high, List<List<String>> matrix) {
        if(root == null) {
            return;
        }
        int mid = low + (high-low)/2;
        
        matrix.get(row).set(mid, String.valueOf(root.val));
        
        setNode(root.left, row+1, low, mid-1, matrix);
        setNode(root.right, row+1, mid+1, high, matrix);
    }
    
    private void initMatrix(int rows, int cols, List<List<String>> matrix) {
        for(int i = 0; i < rows; i++) {
            List<String> row = new ArrayList<String>();
            for(int j = 0; j < cols; j++) {
                row.add("");
            }
            matrix.add(row);
        }
    }
    
    private int height(TreeNode node) {
        if(node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }
}

Follow up