513. Find Bottom Left Tree Value

leetcode medium

#csharp#graph#leetcode#medium#recursion#search#string#tree#two-pointers

Task

Дан корень двоичного дерева, верните самое левое значение в последней строке дерева.

Пример:

Input: root = [2,1,3]

Output: 1

C# solution

matched/original

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

C++ solution

auto-draft, review before submit

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

Java solution

matched/original

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

JavaScript solution

matched/original

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

Python solution

matched/original

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

Go solution

matched/original

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

Explanation

Algorithm

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

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

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

😎