数据结构与算法之LeetCode-515. 在每个树行中找最大值（DFS，BFS）

515. 在每个树行中找最大值 - 力扣（LeetCode）

medium

513. 找树左下角的值 - 力扣（LeetCode）的延伸，同样是求层次的数据

DFS

• 先序遍历，再深度遍历获取每一层的数值

var largestValues = function(root){
  if(!root){
    return []
  }
  
  const res = [];
  const levelOrder = (res,root,level) => {
    if(level === res.length){
      res.push(root.val);
    }else{
      res.splice(level,1,Math.max(res[level],root.val));
    }
    
    if(root.left){
      levelOrder(res,root.left,level+1);
    }
    
    if(root.right){
      levelOrder(res,root.right,level+1);
    }
  }
  
  levelOrder(res,root,0)
  return res;
}
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

执行结果：通过

执行用时：68 ms, 在所有 JavaScript 提交中击败了91.17%的用户

内存消耗：46.1 MB, 在所有 JavaScript 提交中击败了16.84%的用户

通过测试用例：78 / 78

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var largestValues = function(root) {
    let levelMap = new Map();
    if(!root){
        return [];
    }

    let res =  [];
    const levelOrder = (root,level,res)=>{
        if(level === res.length){
            res.push(root.val)
        }else{
            res.splice(level,1,Math.max(res[level],root.val))
        }
        
        if(!root){
            return;
        }

        if(levelMap.size == level){
            levelMap.set(level,root.val)
        }else{
            let maxVal = Math.max(levelMap.get(level),root.val);
            levelMap.set(level,maxVal);
        }


        if(root.left){
            levelOrder(root.left,level+1,res)
        }

        if(root.right){
            levelOrder(root.right,level+1,res)
        }
    }

    levelOrder(root,0,res)
    //return res;
    return Array.from(levelMap.values())

};
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

执行结果：通过

执行用时：68 ms, 在所有 JavaScript 提交中击败了91.17%的用户

内存消耗：46 MB, 在所有 JavaScript 提交中击败了24.44%的用户

通过测试用例：78 / 78

BFS

var largestValues = (root) => {
  let levelMap = [];
  
  if(!root){
    return [];
  }
  
  let queue = [];
  
 	queue.push(root);
  while(queue.length){
    let size = queue.length;
    let curMax = -Infinity;
    
    for(let i=0;i<size;i++){
      let node = queue.shift();
      if(node.left){
        queue.push(node.left)
      }
      if(node.right){
        queue.push(node.right);
      }
      curMax = Math.max(curMax,node.val);
    }
    levelMap.push(curMax)
  }
  
  return levelMap;
}
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

var largestValues = function(root) {
    if (!root) {
        return [];
    }
    const res = [];
    const queue = [root];
    while (queue.length) {
        let len = queue.length;
        let maxVal = -Number.MAX_VALUE;
        while (len > 0) {
            len--;
            const t = queue.shift();
            maxVal = Math.max(maxVal, t.val);
            if (t.left) {
                queue.push(t.left);
            }
            if (t.right) {
                queue.push(t.right);
            }
        }
        res.push(maxVal);
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

执行结果：通过

执行用时：72 ms, 在所有 JavaScript 提交中击败了79.26%的用户

内存消耗：45.8 MB, 在所有 JavaScript 提交中击败了43.84%的用户

通过测试用例：78 / 78

参考链接

515. 在每个树行中找最大值 - 力扣（LeetCode）

在每个树行中找最大值 - 在每个树行中找最大值 - 力扣（LeetCode）

【宫水三叶】树的搜索运用题 - 在每个树行中找最大值 - 力扣（LeetCode）

在每个树行中找最大值【BFS和DFS】 - 在每个树行中找最大值 - 力扣（LeetCode）