|
64 | 64 | */ |
65 | 65 | publicclass_655 { |
66 | 66 |
|
67 | | -/** |
68 | | - * Reference: https://discuss.leetcode.com/topic/98381/java-recursive-solution |
69 | | - * and https://leetcode.com/articles/print-binary-tree/ |
70 | | - */ |
71 | | -publicList<List<String>>printTree(TreeNoderoot) { |
72 | | -List<List<String>>result =newLinkedList<>(); |
73 | | -intheight =root ==null ?1 :getHeight(root); |
74 | | -introws =height; |
75 | | -intcolumns = (int) (Math.pow(2,height) -1); |
76 | | -List<String>row =newArrayList<>(); |
77 | | -for (inti =0;i <columns;i++) { |
78 | | -row.add(""); |
79 | | - } |
80 | | -for (inti =0;i <rows;i++) { |
81 | | -result.add(newArrayList<>(row)); |
| 67 | +publicstaticclassSolution1 { |
| 68 | + |
| 69 | +/** |
| 70 | + * Reference: https://discuss.leetcode.com/topic/98381/java-recursive-solution |
| 71 | + * and https://leetcode.com/articles/print-binary-tree/ |
| 72 | + */ |
| 73 | +publicList<List<String>>printTree(TreeNoderoot) { |
| 74 | +List<List<String>>result =newLinkedList<>(); |
| 75 | +intheight =root ==null ?1 :getHeight(root); |
| 76 | +introws =height; |
| 77 | +intcolumns = (int) (Math.pow(2,height) -1); |
| 78 | +List<String>row =newArrayList<>(); |
| 79 | +for (inti =0;i <columns;i++) { |
| 80 | +row.add(""); |
| 81 | + } |
| 82 | +for (inti =0;i <rows;i++) { |
| 83 | +result.add(newArrayList<>(row)); |
| 84 | + } |
| 85 | +populateResult(root,result,0,rows,0,columns -1); |
| 86 | +returnresult; |
82 | 87 | } |
83 | | -populateResult(root,result,0,rows,0,columns -1); |
84 | | -returnresult; |
85 | | - } |
86 | 88 |
|
87 | | -privatevoidpopulateResult(TreeNoderoot,List<List<String>>result,introw,inttotalRows,inti,intj) { |
88 | | -if (row ==totalRows ||root ==null) { |
89 | | -return; |
| 89 | +privatevoidpopulateResult(TreeNoderoot,List<List<String>>result,introw,inttotalRows,inti,intj) { |
| 90 | +if (row ==totalRows ||root ==null) { |
| 91 | +return; |
| 92 | + } |
| 93 | +result.get(row).set((i +j) /2,Integer.toString(root.val)); |
| 94 | +populateResult(root.left,result,row +1,totalRows,i, (i +j) /2 -1); |
| 95 | +populateResult(root.right,result,row +1,totalRows, (i +j) /2 +1,j); |
90 | 96 | } |
91 | | -result.get(row).set((i +j) /2,Integer.toString(root.val)); |
92 | | -populateResult(root.left,result,row +1,totalRows,i, (i +j) /2 -1); |
93 | | -populateResult(root.right,result,row +1,totalRows, (i +j) /2 +1,j); |
94 | | - } |
95 | 97 |
|
96 | | -privateintgetHeight(TreeNoderoot) { |
97 | | -if (root ==null) { |
98 | | -return0; |
| 98 | +privateintgetHeight(TreeNoderoot) { |
| 99 | +if (root ==null) { |
| 100 | +return0; |
| 101 | + } |
| 102 | +return1 +Math.max(getHeight(root.left),getHeight(root.right)); |
99 | 103 | } |
100 | | -return1 +Math.max(getHeight(root.left),getHeight(root.right)); |
101 | 104 | } |
102 | 105 | } |