|
Don't spend another minute being angry about yesterday.
不要再浪費(fèi)時(shí)間為昨天而懊惱,。 問(wèn)題描述在二叉樹(shù)的每一行中找到最大的值。 比如 輸入: 1 / \ 3 2 / \ \ 5 3 9 輸出: [1, 3, 9]
問(wèn)題分析：關(guān)于這道題我們最容易想到的也就是BFS,，一層一層遍歷,，然后在每一層中再找出最大值。前面已經(jīng)講過(guò)很多BFS的題,，這題不是很難,。我們來(lái)直接看下代碼。
1public List<Integer> largestValues(TreeNode root) {
2 //LinkedList實(shí)現(xiàn)隊(duì)列
3 Queue<TreeNode> queue = new LinkedList<>();
4 List<Integer> values = new ArrayList<>();
5 if (root != null)
6 queue.add(root);//入隊(duì)
7 while (!queue.isEmpty()) {
8 int max = Integer.MIN_VALUE;
9 int levelSize = queue.size();//每一層的數(shù)量
10 for (int i = 0; i < levelSize; i++) {
11 TreeNode node = queue.poll();//出隊(duì)
12 max = Math.max(max, node.val);//記錄每層的最大值
13 if (node.left != null)
14 queue.add(node.left);
15 if (node.right != null)
16 queue.add(node.right);
17 }
18 values.add(max);
19 }
20 return values;
21}
除了一層一層遍歷以外,，我們還可以使用DFS（深度優(yōu)先搜索算法）來(lái)求解,。我們就以上面的舉例來(lái)畫個(gè)圖分析一下
上面的橙色結(jié)點(diǎn)就是遍歷的順序，看明白了上面的圖,，代碼就很容易寫出來(lái)了,，我們?cè)賮?lái)看下代碼
1public List<Integer> largestValues(TreeNode root) {
2 List<Integer> res = new ArrayList<>();
3 helper(root, res, 1);
4 return res;
5}
6
7//level表示的是第幾層,，集合res中的第一個(gè)數(shù)據(jù)表示的是
8// 第一層的最大值，第二個(gè)數(shù)據(jù)表示的是第二層的最大值……
9private void helper(TreeNode root, List<Integer> res, int level) {
10 if (root == null)
11 return;
12 //如果走到下一層了直接加入到集合中
13 if (level == res.size() + 1) {
14 res.add(root.val);
15 } else {
16 //注意：我們的level是從1開(kāi)始的,，也就是說(shuō)root
17 // 是第一層,，而集合list的下標(biāo)是從0開(kāi)始的，
18 // 所以這里level要減1,。
19 // Math.max(res.get(level - 1), root.val)表示的
20 // 是遍歷到的第level層的root.val值和集合中的第level
21 // 個(gè)元素的值哪個(gè)大,，就要哪個(gè)。
22 res.set(level - 1, Math.max(res.get(level - 1), root.val));
23 }
24 //下面兩行是DFS的核心代碼
25 helper(root.left, res, level + 1);
26 helper(root.right, res, level + 1);
27}
|
