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

Examples

Input: root = [1, 2]

Output:

[

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

["2", "", ""]

]

Solutions

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

/**
 * 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

Previous645. Set Mismatch Next658. Find K Closest Elements

Last updated 4 years ago

Was this helpful?