Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate nodes. (The values of the nodes may still be duplicates.)

Left boundary is defined as the path from root to the left-most node. Right boundary is defined as the path from root to the right-most node. If the root doesn't have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not applies to any subtrees.

The left-most node is defined as a leaf node you could reach when you always firstly travel to the left subtree if exists. If not, travel to the right subtree. Repeat until you reach a leaf node.

The right-most node is also defined by the same way with left and right exchanged.

* Method 1: Loop find all left and right, dfs to find the leaves.

```Java

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

class Solution {

public List<Integer> boundaryOfBinaryTree(TreeNode root) {

// first get the left boundry.

List<Integer> result = new ArrayList<>();

TreeNode cur = null;

if(root == null) return result;

if(root.left == null && root.right == null){

result.add(root.val);

return result;

}

List<Integer> left = new ArrayList<>();

cur = root.left;

while(cur != null){

left.add(cur.val);

cur = cur.left != null ? cur.left: cur.right;

}

cur = root.right;

List<Integer> right = new ArrayList<>();

while(cur != null){

right.add(cur.val);

cur = cur.right != null ? cur.right: cur.left;

}

List<Integer> leaves = new ArrayList<>();

dfs(root, leaves);

result.add(root.val);

result.addAll(left);

for(int i = ((left.size() != 0 && left.get(left.size() - 1) == leaves.get(0)) ? 1: 0);

i < (right.size() != 0 && leaves.get(leaves.size() - 1) == right.get(right.size() - 1) ? leaves.size() - 1: leaves.size());

i++) result.add(leaves.get(i));

for(int i = right.size() - 1; i >= 0; i--) result.add(right.get(i));

return result;

}

private void dfs(TreeNode node, List<Integer> list){

if(node.left == null && node.right == null){

list.add(node.val);

return;

}

if(node.left != null) dfs(node.left, list);

if(node.right != null) dfs(node.right, list);

}

}

```

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

* push(int x), which pushes an integer x onto the stack.

* pop(), which removes and returns the most frequent element in the stack.

* If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

Note:

1. Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.

2. It is guaranteed that FreqStack.pop() won't be called if the stack has zero elements.

3. The total number of FreqStack.push calls will not exceed 10000 in a single test case.

4. The total number of FreqStack.pop calls will not exceed 10000 in a single test case.

5. The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.

* Method 1: Map + Deque

* We have one map saving the value and frequency.

* We have another map, key is appearance freqency and value is a deque.

* We always maintain the max appearance number.

* We can take the value out of the stack in the entry and update the maxCount. Meanwhile we update the value and frequency map.

```Java

class FreqStack {

private int maxCount;

private Map<Integer, Integer> freqMap; // k: val, v: freq

private Map<Integer, Deque<Integer>> countMap; // k: freq, v: Stack of values that appears k key times.

public FreqStack() {

this.freqMap = new HashMap<>();

this.countMap = new HashMap<>();

}

public void push(int x) {

freqMap.put(x, freqMap.getOrDefault(x, 0) + 1);

int freq = freqMap.get(x);

maxCount = Math.max(maxCount, freq);

Deque<Integer> stack = countMap.getOrDefault(freq, new ArrayDeque<>());

stack.push(x);

countMap.put(freq, stack);

}

public int pop() {

int val = countMap.get(maxCount).pop();

freqMap.put(val, freqMap.get(val) - 1);

if(countMap.get(maxCount).size() == 0){

countMap.remove(maxCount);

maxCount--;

}

while(!countMap.containsKey(maxCount) && maxCount > 0){

maxCount--;

}

return val;

}

}

/**

* Your FreqStack object will be instantiated and called as such:

* FreqStack obj = new FreqStack();

* obj.push(x);

* int param_2 = obj.pop();

*/

```

1. [Java - intuition and thought process](https://leetcode.com/problems/maximum-frequency-stack/discuss/289916/Java-intuition-and-thought-process)

On an N x N board, the numbers from 1 to N*N are written boustrophedonically starting from the bottom left of the board, and alternating direction each row. For example, for a 6 x 6 board, the numbers are written as follows:


You start on square 1 of the board (which is always in the last row and first column). Each move, starting from square x, consists of the following:

* You choose a destination square S with number x+1, x+2, x+3, x+4, x+5, or x+6, provided this number is <= N*N.

* (This choice simulates the result of a standard 6-sided die roll: ie., there are always at most 6 destinations, regardless of the size of the board.)

* If S has a snake or ladder, you move to the destination of that snake or ladder. Otherwise, you move to S.

A board square on row r and column c has a "snake or ladder" if board[r][c] != -1. The destination of that snake or ladder is board[r][c].

Note that you only take a snake or ladder at most once per move: if the destination to a snake or ladder is the start of another snake or ladder, you do not continue moving. (For example, if the board is `[[4,-1],[-1,3]]`, and on the first move your destination square is `2`, then you finish your first move at `3`, because you do not continue moving to `4`.)

Return the least number of moves required to reach square N*N. If it is not possible, return -1.

Note:

1. 2 <= board.length = board[0].length <= 20

2. board[i][j] is between 1 and N*N or is equal to -1.

3. The board square with number 1 has no snake or ladder.

4. The board square with number N*N has no snake or ladder.

* Method 1: bfs

```Java

class Solution {

public int snakesAndLadders(int[][] board) {

int len = board.length;

if(len <= 1) return 0;

boolean[] visited = new boolean[len * len + 1];

Queue<Integer> q = new LinkedList<>();

q.offer(1);

visited[1] = true;

int step = 0;

while(!q.isEmpty()){

int size = q.size();

for(int k = 0; k < size; k++){

int cur = q.poll();

if(cur == len * len) return step;

for(int d = 1; d <= 6; d++){

int next = cur + d;

int h = len - (next - 1) / len - 1; // line number

int w = (len - 1 - h) % 2 == 0 ? (next - 1) % len: len - 1 - (next - 1) % len;

if(w >= 0 && w < len && h >= 0 && h < len && !visited[next]){

visited[next] = true;

if(board[h][w] == -1) q.offer(next);

else q.offer(board[h][w]);

}

}

}

step++;

}

return -1;

}

}

```