LeetCode 655. Print Binary Tree

ID	Title	Difficulty
1	Two Sum	Easy
2	Add Two Numbers	Medium
3	Longest Substring Without Repeating Characters	Medium
4	Median of Two Sorted Arrays	Hard
5	Longest Palindromic Substring	Medium
6	Zigzag Conversion	Medium
7	Reverse Integer	Medium
8	String to Integer (atoi)	Medium
9	Palindrome Number	Easy
10	Regular Expression Matching	Hard
11	Container With Most Water	Medium
12	Integer to Roman	Medium
13	Roman to Integer	Easy
14	Longest Common Prefix	Easy
15	3Sum	Medium
16	3Sum Closest	Medium
17	Letter Combinations of a Phone Number	Medium
18	4Sum	Medium
19	Remove Nth Node From End of List	Medium
20	Valid Parentheses	Easy
21	Merge Two Sorted Lists	Easy
22	Generate Parentheses	Medium
23	Merge k Sorted Lists	Hard
24	Swap Nodes in Pairs	Medium
25	Reverse Nodes in k-Group	Hard
26	Remove Duplicates from Sorted Array	Easy
27	Remove Element	Easy
28	Find the Index of the First Occurrence in a String	Easy
29	Divide Two Integers	Medium
30	Substring with Concatenation of All Words	Hard
31	Next Permutation	Medium
32	Longest Valid Parentheses	Hard
33	Search in Rotated Sorted Array	Medium
34	Find First and Last Position of Element in Sorted Array	Medium
35	Search Insert Position	Easy
36	Valid Sudoku	Medium
37	Sudoku Solver	Hard
38	Count and Say	Medium
39	Combination Sum	Medium
40	Combination Sum II	Medium
41	First Missing Positive	Hard
42	Trapping Rain Water	Hard
43	Multiply Strings	Medium
44	Wildcard Matching	Hard
45	Jump Game II	Medium
46	Permutations	Medium
47	Permutations II	Medium
48	Rotate Image	Medium
49	Group Anagrams	Medium
50	Pow(x, n)	Medium

JIAKAOBO

LeetCode

感谢赞助!

㊗️
大家
offer
多多！

Problem

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 $2^{h e i g h t + 1} - 1$ .
Place the root node in the middle of the top row (more formally, at location $r e s [0] [(n - 1) / 2]$ ).
For each node that has been placed in the matrix at position res[r][c], place its left child at $r e s [r + 1] [c - 2^{h e i g h t - r - 1}]$ and its right child at $r e s [r + 1] [c + 2^{h e i g h t - 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.

Example 1:

Input: root = [1,2]
Output:
[["","1",""],
 ["2","",""]]

Example 2:

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

Constraints:

The number of nodes in the tree is in the range $[1, 2^{10}]$ .
-99 <= Node.val <= 99
The depth of the tree will be in the range [1, 10].

Code

314. Binary Tree Vertical Order Traversal

class Solution {
    public List<List<String>> printTree(TreeNode root) {
        int height = getHeight(root);

        List<List<String>> res = new ArrayList<>();
        List<String> row = new ArrayList<>();

        for(int i = 0; i < Math.pow(2, height) - 1; i++) {
            row.add("");
        }

        for(int i = 0; i < height; i++) {
            res.add(new ArrayList<>(row));
        }

        helper(res, root, (int)((Math.pow(2, height) - 1) / 2), 0, height);
        return res;
    }

    private void helper(List<List<String>> res, TreeNode curr, int col, int row, int height) {
        if(curr == null) return;

        res.get(row).set(col, curr.val + "");

        int nextRow = row + 1;
        int diff = (int)(Math.pow(2, height - nextRow - 1));
        helper(res, curr.left, col - diff, nextRow, height);
        helper(res, curr.right, col + diff, nextRow, height);
    }

    private int getHeight(TreeNode root) {
        if(root == null) return 0;
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }
}