Java Recursive Solution


  • 11
    public List<List<String>> printTree(TreeNode root) {
        List<List<String>> res = new LinkedList<>();
        int height = root == null ? 1 : getHeight(root);
        int rows = height, columns = (int) (Math.pow(2, height) - 1);
        List<String> row = new ArrayList<>();
        for(int i = 0; i < columns; i++)  row.add("");
        for(int i = 0; i < rows; i++)  res.add(new ArrayList<>(row));
        populateRes(root, res, 0, rows, 0, columns - 1);
        return res;
    }
    
    public void populateRes(TreeNode root, List<List<String>> res, int row, int totalRows, int i, int j) {
        if (row == totalRows || root == null) return;
        res.get(row).set((i+j)/2, Integer.toString(root.val));
        populateRes(root.left, res, row+1, totalRows, i, (i+j)/2 - 1);
        populateRes(root.right, res, row+1, totalRows, (i+j)/2+1, j);
    }
    
    public int getHeight(TreeNode root) {
         if (root == null) return 0;
         return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }
    

  • 0
    T

    Your solution is great! Simulate your method!

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public List<List<String>> printTree(TreeNode root) {
              int h = height(root);
              int w = (int)Math.pow(2,h)-1;
              String[][] strs_array = new String[h][w];
              for(int i=0;i<h;i++){
                  Arrays.fill(strs_array[i],"");
              }
             
            
             constructStringArray(strs_array,0,w,0,root);
             List<List<String>> list_array = new ArrayList<>();
             for(int i=0;i<strs_array.length;i++){
                 list_array.add(Arrays.asList(strs_array[i]));
             }
            
             return list_array;
            
             
        }
        
        public void constructStringArray(String[][] strs_array,int left,int right,int level,TreeNode root){
            if(root == null){
                return;
            }
            
            int mid=(left+right)>>>1;
            strs_array[level][mid]+=root.val;
            constructStringArray(strs_array,left,mid-1,level+1,root.left);
            constructStringArray(strs_array,mid+1,right,level+1,root.right);
        }
        
        public int height(TreeNode root){
            if(root == null){
                return 0;
            }
            int left  = height(root.left);
            int right = height(root.right);
            return Math.max(left,right)+1;
        } 
    }
    
    

  • 0

    Slightly different approach.

    public List<List<String>> printTree(TreeNode root) {
        List<List<String>> ans = new ArrayList<>();
        if (root == null) return ans;
        int level = height (root), size = (int) Math.pow (2, level) - 1;
        for (int l = 0; l < level; l ++) {
            List<String> row = new ArrayList<>();
            for (int s = 0; s < size; s ++) row.add ("");
            ans.add (row);
        }
        ans.get (0).set (size/2, String.valueOf (root.val));
        dfs (ans, root, 0, size/2, (int) Math.pow (2, level - 2));
        return ans;
    }
    
    private void dfs (List<List<String>> ans, TreeNode n, int index, int level, int diff) {
        if (n == null) return;
        if (n.left != null) {
            ans.get (index + 1).set (level - diff, String.valueOf (n.left.val));
            dfs (ans, n.left, index + 1, level - diff, diff/2);
        }
        if (n.right != null) {
            ans.get (index + 1).set (level + diff, String.valueOf (n.right.val));
            dfs (ans, n.right, index + 1, level + diff, diff/2);
        }
    }
    
    private int height (TreeNode n) {
        if (n == null) return 0;
        return Math.max (height (n.left), height (n.right)) + 1;
    }
    

  • 2
    G

    Easier way to initialize List<List<String>>

    public List<List<String>> printTree(TreeNode root) {
        List<List<String>> result = new ArrayList<>();
        int row = getHight(root);
        int col = (int) Math.pow(2, row) - 1;
        List<String> ans = new ArrayList<>();
        for(int i = 0; i < col; i++)  ans.add("");
        for(int i = 0; i < row; i++)  result.add(new ArrayList<>(ans));
        populateResult(root, result, 0, row, 0, col - 1);
        return result;
    }
    
    public void populateResult(TreeNode root, List<List<String>> result, int curRow, int totalRow, int i, int j) {
        if(root == null || curRow == totalRow)  return;
        result.get(curRow).set((i + j) / 2, String.valueOf(root.val));
        populateResult(root.left, result, curRow + 1, totalRow, i, ((i + j) / 2) - 1);
        populateResult(root.right, result, curRow + 1, totalRow, ((i + j) / 2) + 1, j);
    }
    
    public int getHight(TreeNode root) {
        if(root == null)  return 0;
        return 1 + Math.max(getHight(root.left), getHight(root.right));
    }

  • 0
    F

    Very clear logic! Let me explain in details if someone still don't understand this awesome solution.
    According to the observation, in the result matrix, the number of row is the height of tree and the number of columns in each row is 2^(height of tree) – 1.
    So at first, we get the height of the tree.
    Then we generate a result matrix filled with empty space.
    Next, we insert value into each row. And the position of value will be the middle of its own range.
    After understand your logic, I write my own solution. But it's still very similar with yours. lol

    class Solution {
        public List<List<String>> printTree(TreeNode root) {
            List<List<String>> res = new ArrayList();
            int height = 1;
            if (root != null) {
                height = getHeight(root);
            }
            int row = height, col = (int)Math.pow(2, height) - 1;
            ArrayList<String> rows = new ArrayList();
            for (int i = 0; i < col; i++) {
                rows.add("");
            }
            for (int i = 0; i < row; i++) {
                res.add(new ArrayList(rows));
            }
            insertValue(res, root, 0, row, 0, col - 1);
            return res;
        }
        public void insertValue(List<List<String>> res, TreeNode root, int curRow, int totalRow, int start, int end) {
            if (root == null || curRow == totalRow) {
                return;
            }
            res.get(curRow).set((start + end) / 2, Integer.toString(root.val));
            insertValue(res, root.left, curRow + 1, totalRow, start, (start + end) / 2 - 1);
            insertValue(res, root.right, curRow + 1, totalRow, (start + end) / 2 + 1, end);
        }
        public int getHeight(TreeNode root) {
            if (root == null) {
                return 0;
            }
            return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
        }
    }
    

  • 0

    I think there is no need to check '''curRow == totalRow''', because when the curRow is totalRow, the root will definitely be null. I didn't include that in my code, and get passed the OJ.


  • 0
    I

    can I ask a question? in
    for(int i = 0; i < rows; i++) res.add(new ArrayList<>(row));
    if directly res.add(row), the result will be wrong and all the same? Why that happen, there is no use of list in the following part


Log in to reply
 

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