|
7 | 7 |
|
8 | 8 | /** |
9 | 9 | * 545. Boundary of Binary Tree |
| 10 | + * |
10 | 11 | * Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root. |
11 | 12 | * Boundary includes left boundary, addLeaves, and right boundary in order without duplicate nodes. |
12 | 13 | * Left boundary is defined as the path from root to the left-most node. |
|
58 | 59 |
|
59 | 60 | */ |
60 | 61 | publicclass_545 { |
61 | | -publicList<Integer>boundaryOfBinaryTree(TreeNoderoot) { |
62 | | -List<Integer>nodes =newArrayList<>(); |
63 | | -if (root ==null) { |
64 | | -returnnodes; |
65 | | - } |
66 | | - |
67 | | -nodes.add(root.val); |
68 | | -leftBoundary(root.left,nodes); |
69 | | -addLeaves(root.left,nodes); |
70 | | -addLeaves(root.right,nodes); |
71 | | -rightBoundary(root.right,nodes); |
72 | | -returnnodes; |
73 | | - } |
| 62 | +publicstaticclassSolution1 { |
| 63 | +publicList<Integer>boundaryOfBinaryTree(TreeNoderoot) { |
| 64 | +List<Integer>nodes =newArrayList<>(); |
| 65 | +if (root ==null) { |
| 66 | +returnnodes; |
| 67 | + } |
74 | 68 |
|
75 | | -publicvoidleftBoundary(TreeNoderoot,List<Integer>nodes) { |
76 | | -if (root ==null || (root.left ==null &&root.right ==null)) { |
77 | | -/**we don't want to add any LEAVES in leftBoundary and rightBoundary functions either, |
78 | | - * that's why we have the later condition in the if branch.*/ |
79 | | -return; |
80 | | - } |
81 | | -nodes.add(root.val);// add BEFORE child visit |
82 | | -if (root.left ==null) { |
83 | | -leftBoundary(root.right,nodes); |
84 | | - }else { |
| 69 | +nodes.add(root.val); |
85 | 70 | leftBoundary(root.left,nodes); |
| 71 | +addLeaves(root.left,nodes); |
| 72 | +addLeaves(root.right,nodes); |
| 73 | +rightBoundary(root.right,nodes); |
| 74 | +returnnodes; |
86 | 75 | } |
87 | | - } |
88 | 76 |
|
89 | | -publicvoidrightBoundary(TreeNoderoot,List<Integer>nodes) { |
90 | | -if (root ==null || (root.right ==null &&root.left ==null)) { |
91 | | -return; |
92 | | - } |
93 | | -if (root.right ==null) { |
94 | | -rightBoundary(root.left,nodes); |
95 | | - }else { |
96 | | -rightBoundary(root.right,nodes); |
| 77 | +publicvoidleftBoundary(TreeNoderoot,List<Integer>nodes) { |
| 78 | +if (root ==null || (root.left ==null &&root.right ==null)) { |
| 79 | +/**we don't want to add any LEAVES in leftBoundary and rightBoundary functions either, |
| 80 | + * that's why we have the later condition in the if branch.*/ |
| 81 | +return; |
| 82 | + } |
| 83 | +nodes.add(root.val);// add BEFORE child visit |
| 84 | +if (root.left ==null) { |
| 85 | +leftBoundary(root.right,nodes); |
| 86 | + }else { |
| 87 | +leftBoundary(root.left,nodes); |
| 88 | + } |
97 | 89 | } |
98 | | -nodes.add(root.val);// add AFTER child visit(reverse) |
99 | | - } |
100 | 90 |
|
101 | | -publicvoidaddLeaves(TreeNoderoot,List<Integer>nodes) { |
102 | | -if (root ==null) { |
103 | | -return; |
| 91 | +publicvoidrightBoundary(TreeNoderoot,List<Integer>nodes) { |
| 92 | +if (root ==null || (root.right ==null &&root.left ==null)) { |
| 93 | +return; |
| 94 | + } |
| 95 | +if (root.right ==null) { |
| 96 | +rightBoundary(root.left,nodes); |
| 97 | + }else { |
| 98 | +rightBoundary(root.right,nodes); |
| 99 | + } |
| 100 | +nodes.add(root.val);// add AFTER child visit(reverse) |
104 | 101 | } |
105 | | -if (root.left ==null &&root.right ==null) { |
106 | | -nodes.add(root.val); |
107 | | -return; |
| 102 | + |
| 103 | +publicvoidaddLeaves(TreeNoderoot,List<Integer>nodes) { |
| 104 | +if (root ==null) { |
| 105 | +return; |
| 106 | + } |
| 107 | +if (root.left ==null &&root.right ==null) { |
| 108 | +nodes.add(root.val); |
| 109 | +return; |
| 110 | + } |
| 111 | +addLeaves(root.left,nodes); |
| 112 | +addLeaves(root.right,nodes); |
108 | 113 | } |
109 | | -addLeaves(root.left,nodes); |
110 | | -addLeaves(root.right,nodes); |
111 | 114 | } |
112 | 115 |
|
113 | 116 | } |