Java simple solution


  • 0
    A
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        StringBuilder[] strList = new StringBuilder[10];
        HashMap<TreeNode, Integer> nodeToColumnIdx = new HashMap<>();
        int maxWidth = 0;
        public List<List<String>> printTree(TreeNode root) {
            List<List<String>> result = new ArrayList<>();
            if (root == null) return result;
            int h = getHeight(root, 0);
            //System.out.println(h);
            maxWidth = (1 << h) - 1;
            //System.out.println(maxWidth);
            for (int i = 0; i < h; i++) {
                List<String> row = new ArrayList<>();
                result.add(row);
                for (int j = 0; j < maxWidth; j++) {
                    row.add("");
                }
            }
            dfs(root, 0, result, 0, maxWidth - 1);
            return result;
        }
        
        public void dfs(TreeNode root, int h, List<List<String>> result, int start, int end) {
            if (root == null) return;
            List<String> row = result.get(h);
            int colIdx = (start + end) / 2;
            row.set(colIdx, Integer.toString(root.val));
            dfs(root.left, h + 1, result, start, colIdx - 1);
            dfs(root.right, h + 1, result, colIdx + 1, end);
        }
        
        public int getHeight(TreeNode node, int parentHeight) {
            int leftH = 0, rightH = 0;
            int currheight = parentHeight + 1;
            if (node.left != null) leftH = getHeight(node.left, parentHeight + 1);
            if (node.right != null) rightH = getHeight(node.right, parentHeight + 1);
            return Math.max(leftH, Math.max(rightH, currheight));
        }
    }
    

Log in to reply
 

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