search

leetcode-pp / 91alg-14-daily-check

0 stars 0 forks source link

【Day 16 】2024-08-30 - 513. 找树左下角的值 #22

Open azl397985856 opened 2 weeks ago

azl397985856 commented 2 weeks ago

513. 找树左下角的值

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/find-bottom-left-tree-value/

前置知识

暂无

题目描述

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

输入:

    2
   / \
  1   3

输出:
1
 

示例 2:

输入:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

输出:
7
 
akxuan commented 2 weeks ago

求的就是每层的index 0. 时间复杂度 O(N) number of node space O(N) , 就是 q 的长度， q 最长是1/2 N， 所以是O（N）

 def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        #层序遍历求每行的第一个值
        if root is None: 
            return 0
        q = deque()
        q.append(root)
        result = 0 
        while q: 
            size = len(q)
            for i in range(size):
                node = q.popleft()
                if i == 0 :
                    result = node.val
                if node.left: 
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return result
AllanLi-LHH commented 2 weeks ago

Method1

BFS reversed level order traversal,

Code

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        TreeNode cur = null;
        while(!queue.isEmpty()){
            cur = queue.poll();
            // offer the right child node into the queue
            if(cur.right != null){queue.offer(cur.right);}
            if(cur.left != null){ queue.offer(cur.left);}
        }
        return cur.val;
    }
}

复杂度分析

Method 2

DFS preorder traversal. Find out the first occurrence of node with the longest path from the root node. Recursive order guarantees the leftmost node of the bottom level could be visited firstly.

Code

class Solution {
    private TreeNode ans = null;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 0, new int[]{Integer.MIN_VALUE});
        return ans.val;
    }
    private void dfs(TreeNode root, int len, int[] maxlen){
        if(root == null){
            return;
        }
        if(len> maxlen[0]){
            ans = root;
            maxlen[0] = len;
        }
        dfs(root.left, len+1, maxlen);
        dfs(root.right, len+1, maxlen);
    }
}

复杂度分析

ith value in last row:

class Solution {
    private TreeNode ans = null;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 0, new int[]{Integer.MIN_VALUE}, new int[]{0}, 5);
        return ans.val;
    }
    private void dfs(TreeNode root, int len, int[] maxlen, int[] k, int i){
        if(root == null){
            return;
        }
        if(len> maxlen[0]){
            k[0] = 1;
        }
        if(len == maxlen[0]){
            k[0]++;
            if(k[0] == i){
                ans = root;
            }
        }
        maxlen[0] = Math.max(maxlen[0], len);
        dfs(root.left, len+1, maxlen, k, i);
        dfs(root.right, len+1, maxlen, k, i);
    }
}
zjy-debug commented 2 weeks ago

思路

在每次访问节点时，检查当前深度是否大于之前记录的最大深度。如果是，则更新最大深度和对应的节点值；首先递归调用左子树，增加深度；然后递归调用右子树，同样增加深度。

代码

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        self.maxHeight = -1
        self.leftmostValue = 0

        def findLeft(node: TreeNode, height: int):
            if node is None:
                return

            if height > self.maxHeight:
                self.maxHeight = height
                self.leftmostValue = node.val

            findLeft(node.left, height + 1)
            findLeft(node.right, height + 1)

        findLeft(root, 0)
        return self.leftmostValue

复杂度：

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

huizsh commented 2 weeks ago 
# 思路：层序遍历，找最底层第一个节点的值
# 时间复杂度：O（n)
# 空间复杂度：O (m) m是单层最多的结点数
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        q = deque()
        q.append(root)
        while len(q) != 0:
            num = len(q)
            q1 = deque()
            for i in range(num):
                item = q.popleft()
                if i == 0:
                    result = item.val
                if item.left:
                    q1.append(item.left)
                if item.right:
                    q1.append(item.right)
            q = q1
        return result
CelesteXiong commented 2 weeks ago

Intuition

BFS

Algorithm

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        if not root: return []
        queue = [(root, 0)]
        result = root.val
        last_level = 0
        while queue:
            node, cur_level = queue.pop(0)
            if last_level < cur_level: 
                result = node.val
                last_level = cur_level
            if node.left: 
                queue.append((node.left, cur_level+1))
            if node.right:
                queue.append((node.right, cur_level+1))

        return result

Complexity

Time: O(n), n is the number of nodes

Space: O(n)

peggyhao commented 2 weeks ago 
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int ret = 0;
        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode p = queue.poll();
            if (p.right != null) {
                queue.offer(p.right);
            }
            if (p.left != null) {
                queue.offer(p.left);
            }
            ret = p.val;
        }
        return ret;
    }
}
godkun commented 2 weeks ago

思路

代码

TS实现

function findBottomLeftValue(root: TreeNode | null): number {
  let queue: TreeNode[] = [root];
  let bottomLeftValue: number | null = null;

  while (queue.length > 0) {
    const levelSize = queue.length;
    for (let i = 0; i < levelSize; i++) {
      const currentNode = queue.shift()!;
      if (i === 0) bottomLeftValue = currentNode.val;
      if (currentNode.left) queue.push(currentNode.left);
      if (currentNode.right) queue.push(currentNode.right);
    }
  }

  return bottomLeftValue;
}

复杂度分析

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

Fightforcoding commented 2 weeks ago

Algorithm

DFS


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        def dfs(node, depth):
            nonlocal max_depth, bottom_left_value

            if not node:
                return
            if depth > max_depth:
                max_depth = depth
                bottom_left_value = node.val
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

        max_depth = -1
        bottom_left_value = root.val
        dfs(root, 0)
        return bottom_left_value

Time O(n) Space O(h) where h is the max height of the tree