发表于 | 分类于

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

1
[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

1
[[1,2,6], [1,3,5], [2,3,4]]

解法1：

典型的backtracking的题目，用一般的模板就能解决。用一个helper函数，用一个数保存当前试的数的起始位置， 用一个vector存储当前选出的答案。
要注意的是退出条件。 同时注意到由于存在可能计算重复的数据，所以memorization可以帮助efficiency，不过下面的答案没有用。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> temp;
        vector<vector<int>> res;
        int num = 1; 
        int max = 9;
        helper(temp, res, k, n, num, max);
        return res;
    }
    
    void helper(vector<int>& cur, vector<vector<int>>& res, int k, int n, int num, int max) {
        
        if (n < 0 || (k == 0 && n > 0) || (n == 0 && k != 0)) {
            return;
        }
        
        if (n == 0 && k == 0) {
            res.push_back(cur);
            return;
        }
        
        for (int i = num; i <= max; ++i) {
            cur.push_back(i);
            helper(cur, res, k - 1,n - i, i + 1, max);
            cur.pop_back();
        }
        
    }
};

Java

1

发表于 | 分类于

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

解法1： Math

数学题，解法就不重复了，第一位取值每(n - 1)!变化一位，第二位取值每（n - 2)% 变化一位。 通过k / (n - i)! 算出来的是index， 这就意味着每次取完一个数以后要把那个数删除。

C++

1
c++ 里面vector的初始化如果用vector<int> (n, initial_value)的形式要注意是“（”， 不是“{“， 花括号是给了一组初始的array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> number ;
        int perm = 1;
        for (int i = 1; i <= n; ++i) {
            number.push_back(i);
            perm *= i;
        }
        
        k--;
        string res;
        for (int i = 0; i < n; ++i) {
            perm /= (n - i);
            int choosed = k / perm;
            k %= perm;
            res += to_string(number[choosed]);
            number.erase(number.begin() + choosed);
        }
        return res;
    }
};

Java

1

发表于 | 分类于

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example:
Given a binary tree {1,2,3,4,5},

1
2
3
4
5
    1
   / \
  2   3
 / \
4   5

return the root of the binary tree [4,5,2,#,#,3,1].

1
2
3
4
5
  4
 / \
5   2
   / \
  3   1

解法1：

用分治的方法思考比较容易， 题目的意思是只有两种情况，一种是没有右子树，但可能有左子树，一种是有右子树但一定也有左子树。
变换之后，right tree变成left， root变成left， 而原来的left也需要进行upside down的变化。最后他的root是最终的root， 而他的最右子树变成了现在root和right的parent
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
struct res {
    TreeNode* root;
    TreeNode* tail;
    res(TreeNode* r, TreeNode* t):root(r),tail(t) {}
};
class Solution {
public:
    TreeNode* upsideDownBinaryTree(TreeNode* root) {
        res result = helper(root);
        return result.root;
    }
    res helper(TreeNode* root) {
        if (!root) {
            return res(NULL, NULL);
        }
        if (!root->left && !root->right) {
            return res(root, root);
        }
        res left = helper(root->left);
        left.tail->left = root->right;
        left.tail->right = root;
        root->left = NULL;
        root->right = NULL;
        return res(left.root, root);
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    class NodeMark {
        TreeNode root;
        TreeNode tail;
        public NodeMark(TreeNode root, TreeNode tail) {
            this.root = root;
            this.tail = tail;
        }
    };
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null) return root;
        NodeMark temp = helper(root);
        return temp.root;
    }
    private NodeMark helper(TreeNode root) {
        if (root == null) {
            return new NodeMark(null, null);
        }
        if (root.left == null && root.right == null) {
            return new NodeMark(root, root);
        }
        NodeMark left = helper(root.left);
        left.tail.left = root.right;
        left.tail.right = root;
        root.left = null;
        root.right = null;
        return new NodeMark(left.root, root);
    }
}

发表于 | 分类于

Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = “Hello World”,
return 5.

解法1：

首这题的启发，也用istringstream来读取一个个的word，直到最后一个string。
C++
```
这里要注意的是， getline会读取word直到下一个delimiter的出现，那么如果有两个连续的space，第二个space之前会读出一个“”， 也就是空字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int lengthOfLastWord(string s) {
        istringstream ss(s);
        string word;
        int res = 0;
        while (getline(ss, word, ' ')) {
                if (!word.empty()) {
                    res = word.size();    
                }
        }
        return res;
    }
};

Java

1

解法2：

不用istringstream的操作， 一位位的读。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLastWord(string s) {
        int res = 0;
        int count = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == ' ') {
                if (count != 0) {
                    res = count;
                } 
                count = 0;
            } else {
                ++count;
            }
        }
        if (count) res = count;
        return res;
    }
};

发表于 | 分类于

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:
pattern = “abba”, str = “dog cat cat dog” should return true.
pattern = “abba”, str = “dog cat cat fish” should return false.
pattern = “aaaa”, str = “dog cat cat dog” should return false.
pattern = “abba”, str = “dog dog dog dog” should return false.
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

解法1： HashMap, O(N + M)

这题对于我主要是学习C++的各种知识。。。 主要的思路是用两个map存储p到s的映射，也存储s到p的映射。
C++

1
2
3
4
读取一个string可以用到istringstream, 用法是istringstream ss(str);
然后读取ss中的string可以用getline(const istringstream&, const string& word, char delimiter)
getline如果返回为空则证明stream已经结束。
最后要判断getline是否为空是因为有可能str比pattern长。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool wordPattern(string pattern, string str) {
        istringstream ss(str);
        string word;    // store the word from str
        unordered_map<char, string> p2s;
        unordered_map<string, char> s2p;
        for (auto c : pattern) {
            if (!getline(ss, word, ' ')) {
                return false;
            }
            if (p2s.count(c) && p2s[c] != word) {
                return false;   
            }
            if (s2p.count(word) && s2p[word] != c) {
                return false;
            }
            p2s[c] = word;
            s2p[word] = c;
        }
        
        return !getline(ss, word, ' ');
        
    }
};

Java

1

发表于 | 分类于

Given a binary tree, collect a tree’s nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:
Given binary tree

1
2
3
4
5
6
7
8
9
10
          1
         / \
        2   3
       / \     
      4   5
```  
Returns [4, 5, 3], [2], [1].
Explanation:
1. Removing the leaves [4, 5, 3] would result in this tree:

  1
 /
2          

1
2. Now removing the leaf [2] would result in this tree:
1          

1
3. Now removing the leaf [1] would result in the empty tree:
[]         

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
Returns [4, 5, 3], [2], [1].
### 解法1： DFS ###
这题一开始想用Hashtable把tree转化成一个图然后不停的拨洋葱，后来参考了别人的做法发现不需要这样。 每一个点属于第几层的leave是由他的高度决定的。 那么我们只要遍历一次，算出每一个node的高度，如果高度为0， 那么就是leaf， 放在结果的第一个vector中，如果高度为1，那么放在第二个vector中以此类推。
C++
{% codeblock lang:cpp %}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>> res;
        helper(root, res);
        return res;
    }
    int helper(TreeNode* root, vector<vector<int>>& res) {
        if (!root) {
            return -1;
        }
        int height = max(helper(root->left, res), helper(root->right, res)) + 1;
        if (height >= res.size()) res.resize(height + 1);
        res[height].push_back(root->val);
        return height;
    }
};
{% endcodeblock %}
Java
{% codeblock lang: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<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        helper(root, res);
        return res;
    }
    private int helper(TreeNode root, List<List<Integer>> res) {
        if (root == null) {
            return -1;
        }
        int left = helper(root.left, res);
        int right = helper(root.right, res);
        int depth = Math.max(left, right) + 1;
        if (depth >= res.size()) {
            res.add(new ArrayList<Integer>());
        }
        res.get(depth).add(root.val);
        return depth;
    }
}
{% endcodeblock %}
### 解法2： 剥洋葱 ###
这种解法是用递归的方式不停的remove tree node。 用递归的方式的时候，如果要删掉一个leaf，办法是如果是leaf，则返回null， 而每一次递归的时候root->left = remove(left);
这样返回的NULL就会被赋值给root的left tree，所以就删掉了那个node。
每一次遍历的时候，都返回更新过的root， 直到root被删成空为止。
C++
{% codeblock lang: cpp %}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>> res;
        while (root) {
            vector<int> leaves;
            root = removeLeaves(root, leaves);
            res.push_back(leaves);
        }
        return res;
    }
    TreeNode* removeLeaves(TreeNode* root, vector<int>& leaves) {
        if (!root) {
            return NULL;
        }
        if (!root->left && !root->right) {
            leaves.push_back(root->val);
            return NULL;
        }
        root->left = removeLeaves(root->left, leaves);
        root->right = removeLeaves(root->right, leaves);
        return root;
    }
};
{% endcodeblock %}
```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<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        while (root != null) {
            List<Integer> leaves = new ArrayList<>();
            root = remove(root, leaves);
            res.add(leaves);  
        }
        return res;        
    }
    private TreeNode remove(TreeNode root, List<Integer> leaves) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            leaves.add(root.val);
            return null;
        }
        root.left = remove(root.left, leaves);
        root.right = remove(root.right, leaves);
        return root;
    }
}

发表于 | 分类于

Given preorder and inorder traversal of a tree, construct the binary tree.

解法1： Recursive

Preorder的顺序是root，left，right
inorder的顺序是left，root，right
可见preorder的第一个一定是root，这样有了root的数值，我们就可以在inorder中找到root的位置，左边都是left，右边都是right
对左右子树同时进行tree construction。要注意的是下标容易出错， 要注意。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() != inorder.size()) {
            return NULL;
        }
        return helper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
    TreeNode* helper(vector<int>& preorder, int pstart, int pend, vector<int>& inorder, int istart, int iend) {
        if (pstart > pend || istart > iend) {
            return NULL;
        }
        if (pstart == pend) {
            return new TreeNode(preorder[pstart]);
        }
        int rootval = preorder[pstart];
        TreeNode* root = new TreeNode(rootval);
        auto iter = find(inorder.begin() + istart, inorder.begin() + iend + 1, rootval);
        int leftNum = iter - (inorder.begin() + istart);
        TreeNode* left = helper(preorder, pstart + 1, pstart + leftNum, inorder, istart, istart + leftNum - 1);
        TreeNode* right = helper(preorder, pstart + leftNum + 1, pend, inorder, istart + leftNum + 1, iend);
        root->left = left;
        root->right = right;
        return root;
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(0, 0, inorder.length - 1, preorder, inorder);
    }
    public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (preStart > preorder.length - 1 || inStart > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        int inIndex = 0; // Index of current root in inorder
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) {
                inIndex = i;
            }
        }
        root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
        root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
        return root;
    }
}

发表于 | 分类于

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

1
2
3
4
5
1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

解法1： Recursive, Divide & Conquer

用分治的思想考虑会比较容易，从1到n，如果选择了i，那么1到i-1所能组成的tree都是i的左子树，i+1到n都为右子树。对于每一颗左子树和右子树的组合，我们都能构建一个新的树。
用递归的方式很容易解决。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> res;
        if (n == 0) {
            return res;
        }
        return generate(1, n);
    }
    vector<TreeNode*> generate(int start, int end) {
        vector<TreeNode*> res;
        if (start > end) {
            res.push_back(NULL);
            return res;
        }
        for (int i = start; i<= end; ++i) {
            vector<TreeNode*> left = generate(start, i -1);
            vector<TreeNode*> right = generate(i + 1, end);
            for (TreeNode* l: left) {
                for (TreeNode* r: right) {
                    TreeNode* root = new TreeNode(i);
                    root->left = l;
                    root->right = r;
                    res.push_back(root);
                }
            }
        }
        return res;
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> res = new ArrayList<>();
        if (n <= 0) {
            return res;
        }
        return generateTrees(1, n);
    }
    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> res = new ArrayList<>();
        if (start > end) {
            return res;
        }
        if (start == end) {
            res.add(new TreeNode(start));
            return res;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = generateTrees(start, i - 1);
            List<TreeNode> right = generateTrees(i + 1, end);
            if (left.isEmpty()) {
                for (TreeNode x : right) {
                    TreeNode root = new TreeNode(i);
                    root.right = x;
                    res.add(root);
                }
            } else if (right.isEmpty()) {
                for (TreeNode x : left) {
                    TreeNode root = new TreeNode(i);
                    root.left = x;
                    res.add(root);
                }
            } else {
                for (TreeNode l : left) {
                    for (TreeNode r : right) {
                        TreeNode root = new TreeNode(i);
                        root.left = l;
                        root.right = r;
                        res.add(root);
                    }
                }
            }
        }
        return res;
    }
}

发表于 | 分类于

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

1
2
3
4
5
  0
  |
  1
 / \
2   3

return 1

Example 2:

1
2
3
4
5
6
7
8
9
Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
     0  1  2
      \ | /
        3
        |
        4
        |
        5

return [3, 4]

解法1： O(N) Time + O(N) Space

这题有些难度。。一开始自己想了O(N*N)的算法，果断TLE了。 这里的解法是参考了Discussion里的一个解法。
首先要观察， 看对于一个图最多有几个可能的MHT， 答案是最多有两个。 为什么呢？假设有1个，那么就是自己。
假设有两个节点，则无论他们是否连接， 其中任何一个作为节点高度都是一样的。
如果只有三个节点， 那么如果有两个线连着，那么有两个叶子和一个中间点，那个中间点就是MHT。
有了这个思路， 我们可以从leaf出发，不停的向图中间靠拢，直到没有leaf为止（leaf定义为有且仅有一条边界）/

C++

1
2
3
可以用unordered_set<int>来表示children， 对应的操作有erase（）， insert（）
C++中有std::swap可以用来交换两个container中的数据。
vector可以用vector.clear()来清除里面的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        vector<int> res;
        if (n == 1) {
            res.push_back(0);
            return res;
        }
        if (n == 2) {
            res.push_back(0);
            res.push_back(1);
            return res;
        }
        // Construct the tree
        unordered_map<int, unordered_set<int>> map;
        for (auto p : edges) {
            if (!map.count(p.first)) {
                map[p.first] = unordered_set<int>();
            }
            if (!map.count(p.second)) {
                map[p.second] = unordered_set<int>();
            }
            map[p.first].insert(p.second);
            map[p.second].insert(p.first);
        }
        // Remove leaves until we have only 1 or 2 nodes
        vector<int> leaves;
        for (int i = 0; i < n; ++i) {
            if (map[i].size() == 1) {
                leaves.push_back(i);
            }
        }
        vector<int> newLeaves;
        while (true) {
            for (int leaf : leaves) {
                unordered_set<int> innerLayer = map[leaf];
                for (int node : innerLayer) {
                    map[node].erase(leaf);
                    if (map[node].size() == 1) {
                        newLeaves.push_back(node);
                    }
                }
            }
            if (newLeaves.empty()) {
                return leaves;
            }
            leaves.clear();
            swap(leaves, newLeaves);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        if (n == 1) {
            res.add(0);
            return res;
        }
        if (n == 2) {
            res.add(0);
            res.add(1);
            return res;
        }
        if (edges == null || edges.length == 0 || edges[0] == null || edges[0].length == 0) {
            return res;
        }
        // BFS and 剥洋葱
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] edge: edges) {
            int start = edge[0];
            int end = edge[1];
            if (!map.containsKey(start)) {
                map.put(start, new HashSet<>());
            }
            if (!map.containsKey(end)) {
                map.put(end, new HashSet<>());
            }
            map.get(start).add(end);
            map.get(end).add(start);
        }
        // Doing a bfs
        Queue<Integer> queue = new LinkedList<>();
        for (int key : map.keySet()) {
            if (map.get(key).size() == 1) {
                queue.offer(key);
            }
        }
        // Doing a peel-an-onion algorithm
        while ( n > 2) {
            int size = queue.size();    // number of leaf nodes at this time
            n -= size;
            for (int i = 0; i < size; i++) {
                int node = queue.poll();
                Set<Integer> connected = map.get(node);
                for (int c : connected) {
                    map.get(c).remove(node);
                    if (map.get(c).size() == 1) {
                        queue.offer(c); // next round onion peel
                    }
                }
            }
        }
        while (!queue.isEmpty()) {
            res.add(queue.poll());
        }
        return res;
    }
}