【基础篇 - Day 16】 2023-02-28 - 513. 找树左下角的值 （03. 树 ）

[threedayAAAAA]

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

 

示例 1:

输入: root = [2,1,3] 输出: 1 示例 2:

输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7  

提示:

二叉树的节点个数的范围是 [1,104] -231 <= Node.val <= 231 - 1 

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/find-bottom-left-tree-value 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

思路一

思路

层序遍历

代码

function findBottomLeftValue(root: TreeNode | null, dep = 0): number {
    let result = 0
    let floor = [root]
    while(floor.length){
        result = floor[0].val
        let newFloor = []
        floor.forEach(item => {
            if(item.left)  newFloor.push(item.left)
            if(item.right) newFloor.push(item.right)
        })
        floor = newFloor
    }
    return result
};

时空复杂度

• 时间复杂度：O(N)
• 空间复杂度: O(Max(Len(floor)))

思路二

思路

深序遍历

代码

function findBottomLeftValue(root: TreeNode | null, dep = 0): number {
    let result = [root.val, -1]
    function help(root: TreeNode, dep = 0){
        if(root.left){
            help(root.left, dep + 1)
        }
        if(root.right){
            help(root.right, dep + 1)
        }
        if(!root.left && !root.right){
            if(dep > result[1]){
                result = [root.val, dep]
            }
        }
    }
    help(root)
    return result[0]
};

时空复杂度

• 时间复杂度：O(N)
• 空间复杂度： O(LogN)

[MiumMi]

思路

层序遍历，找到最左边的节点即可，这里是优先填入的右节点，保证最后拿到的一定是左节点

代码

function findBottomLeftValue(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }
    let queue = [root];
    let lastVal = root.val;
    while(queue.length) {
        const currentLevel = queue;
        queue = [];
        for (let i = 0; i < currentLevel.length; i++) {
            const currentNode = currentLevel[i];
            lastVal = currentNode.val;
            if (currentNode.right) {
                queue.push(currentNode.right);
            }
            if (currentNode.left) {
                queue.push(currentNode.left);
            }
        }
    }
    return lastVal;
};

---

分析

1. 时间复杂度：O(n)
2. 空间复杂度：O(n)

[yunliuyan]

思路

• BFS遍历
• 从右到左开始遍历，最后一个树节点即为最左节点

代码

function findBottomLeftValue(root: TreeNode | null): number {
  let bootomLeft: TreeNode = root;
  const queue: TreeNode[] = [];
  if (root) { 
    queue.unshift(root);
  }
  while(queue.length) {
    const curNode = queue.pop();
    if (curNode?.right) {
      queue.unshift(curNode.right);
    }
    if (curNode?.left) {
      queue.unshift(curNode.left);
    }
    bootomLeft = curNode;
  }
  return bootomLeft?.val ?? 0;
};

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(n)