数据结构与算法之LeetCode-513. 找树左下角的值 - 力扣（DFS，BFS）

513. 找树左下角的值 - 力扣（LeetCode）

DFS

/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function(root) {
    // 层序遍历
    // 每一层取左端点的数值

    // const res  = [];
    const levelOrder = (node,level,position)=>{
        if(!node){
            return;
        }else{
            // res.push({
            //     level,
            //     val:node.val??0,
            //     position
            // });
        }

        
        if(node.left){
            levelOrder(node.left,level+1,'left')
        }
        if(node.right){
            levelOrder(node.right,level+1,'right')
        }

        if(level+1>curLevel){
            curLevel = level+1;
            curVal = node.val;
        }
    }

    let curLevel = 0,curVal=0;
    levelOrder(root,0,'left');
    return curVal;

    // res.sort((a,b)=>a.level-b.level)

    // for(let i=res.length-1;i>=0;i--){
    //     if(res[i].position == 'left'){
    //         return res[i].val;
    //     }
    // }


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

执行结果：通过

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

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

通过测试用例：76 / 76

var findBottomLeftValue = function(root){
  const dfs = (root,height)=>{
    if(!root){
      return;
    }
    
    height++;
    dfs(root.left,height);
    dfs(root.right,height);
    
    if(height>curHeight){
    	curHeight = height;
      curVal = root.val;
    }
  }
  
  let curHeight = 0,curVal = 0;
  dfs(root,0);
  return curVal;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

执行结果：通过

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

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

通过测试用例：76 / 76

BFS

• 遍历每一层节点，遍历每一个节点时，需要先把它的非空右子节点放入队列，然后再把非空左子节点放入队列，这样才能保证从右到左遍历每一层节点
• BFS所遍历的最后一个节点的值就是最底层最左边的节点

var findBottomLeftValue = function(root){
  let res = 0;
  const queue = [root];
  while(queue.length){
    const p = queue.shift();
    if(p.right){
      queue.push(p.right);
    }
    if(p.left){
      queue.push(p.left);
    }
    
    res = p.val;
  }
  return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

执行结果：通过

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

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

通过测试用例：76 / 76

参考链接

513. 找树左下角的值 - 力扣（LeetCode）

找树左下角的值 - 找树左下角的值 - 力扣（LeetCode）