513. Find Bottom Left Tree Value

public class Solution {
    private int maxDepth = -1;
    private int bottomLeftValue = 0;
    public int FindBottomLeftValue(TreeNode root) {
        Dfs(root, 0);
        return bottomLeftValue;
    }
    private void Dfs(TreeNode current, int depth) {
        if (current == null) return;
        if (depth > maxDepth) {
            maxDepth = depth;
            bottomLeftValue = current.val;
        }
        Dfs(current.left, depth + 1);
        Dfs(current.right, depth + 1);
    }
}
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int maxDepth = -1;
    private int bottomLeftValue = 0;
    public int FindBottomLeftValue(TreeNode root) {
        Dfs(root, 0);
        return bottomLeftValue;
    }
    private void Dfs(TreeNode current, int depth) {
        if (current == null) return;
        if (depth > maxDepth) {
            maxDepth = depth;
            bottomLeftValue = current.val;
        }
        Dfs(current.left, depth + 1);
        Dfs(current.right, depth + 1);
    }
}
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    private int maxDepth = -1;
    private int bottomLeftValue = 0;
    
    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 0);
        return bottomLeftValue;
    }
    
    private void dfs(TreeNode current, int depth) {
        if (current == null) return;
        
        if (depth > maxDepth) {
            maxDepth = depth;
            bottomLeftValue = current.val;
        }
        
        dfs(current.left, depth + 1);
        dfs(current.right, depth + 1);
    }
}

class Solution {
    constructor() {
        this.maxDepth = -1;
        this.bottomLeftValue = 0;
    }
    
    findBottomLeftValue(root) {
        this.dfs(root, 0);
        return this.bottomLeftValue;
    }
    
    dfs(current, depth) {
        if (!current) return;
        
        if (depth > this.maxDepth) {
            this.maxDepth = depth;
            this.bottomLeftValue = current.val;
        }
        
        this.dfs(current.left, depth + 1);
        this.dfs(current.right, depth + 1);
    }
}

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        self.maxDepth = -1
        self.bottomLeftValue = 0
        self.dfs(root, 0)
        return self.bottomLeftValue

    def dfs(self, current: TreeNode, depth: int):
        if not current:
            return
        
        if depth > self.maxDepth:
            self.maxDepth = depth
            self.bottomLeftValue = current.val

        self.dfs(current.left, depth + 1)
        self.dfs(current.right, depth + 1)
        return

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type Solution struct {
    maxDepth       int
    bottomLeftValue int
}

func (s *Solution) findBottomLeftValue(root *TreeNode) int {
    s.maxDepth = -1
    s.bottomLeftValue = 0
    s.dfs(root, 0)
    return s.bottomLeftValue
}

func (s *Solution) dfs(current *TreeNode, depth int) {
    if current == nil {
        return
    }
    
    if depth > s.maxDepth {
        s.maxDepth = depth
        s.bottomLeftValue = current.Val
    }
    
    s.dfs(current.Left, depth+1)
    s.dfs(current.Right, depth+1)
}

Algorithm

Инициализируйте переменную maxDepth для хранения глубины нижнего уровня дерева. Инициализируйте переменную bottomLeftValue для хранения самого левого значения в последней строке дерева.

Реализуйте рекурсивную функцию dfs, которая обходит дерево и находит самое левое значение в последней строке дерева. Параметры функции: current (текущий узел) и depth (его глубина). Проверьте, пуст ли текущий узел. Если да, то вернитесь.

Проверьте, превышает ли текущая глубина глобальную переменную maxDepth. Если да, это значит, что мы нашли новый уровень. Установите maxDepth в значение текущей глубины. Установите bottomLeftValue в значение текущего узла. Рекурсивно вызовите dfs для левого поддерева текущего узла, увеличив глубину на один. Рекурсивно вызовите dfs для правого поддерева текущего узла, увеличив глубину на один. Вызовите dfs с корнем и начальной глубиной 0. Верните bottomLeftValue.

😎