543. Diameter of Binary Tree

leetcode easy

#csharp#easy#graph#leetcode#math#recursion#tree#two-pointers

Task

Учитывая корень бинарного дерева, вернуть длину диаметра дерева.

Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень.

Длина пути между двумя узлами представлена числом ребер между ними.

Пример:

Input: root = [1,2]

Output: 1

C# solution

matched/original

public class Solution {
    private int diameter;
    
    public int DiameterOfBinaryTree(TreeNode root) {
        diameter = 0;
        LongestPath(root);
        return diameter;
    }
    
    private int LongestPath(TreeNode node) {
        if (node == null) return 0;
        
        int leftPath = LongestPath(node.left);
        int rightPath = LongestPath(node.right);
        
        diameter = Math.Max(diameter, leftPath + rightPath);
        
        return Math.Max(leftPath, rightPath) + 1;
    }
}

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 diameter;
    
    public int DiameterOfBinaryTree(TreeNode root) {
        diameter = 0;
        LongestPath(root);
        return diameter;
    }
    
    private int LongestPath(TreeNode node) {
        if (node == null) return 0;
        
        int leftPath = LongestPath(node.left);
        int rightPath = LongestPath(node.right);
        
        diameter = max(diameter, leftPath + rightPath);
        
        return max(leftPath, rightPath) + 1;
    }
}

Java solution

matched/original

class Solution {
    private int diameter;
    
    public int diameterOfBinaryTree(TreeNode root) {
        diameter = 0;
        longestPath(root);
        return diameter;
    }
    
    private int longestPath(TreeNode node) {
        if (node == null) return 0;
        
        int leftPath = longestPath(node.left);
        int rightPath = longestPath(node.right);
        
        diameter = Math.max(diameter, leftPath + rightPath);
        
        return Math.max(leftPath, rightPath) + 1;
    }
}

JavaScript solution

matched/original

class Solution {
    constructor() {
        this.diameter = 0;
    }
    
    diameterOfBinaryTree(root) {
        this.diameter = 0;
        this.longestPath(root);
        return this.diameter;
    }
    
    longestPath(node) {
        if (node === null) return 0;
        
        let leftPath = this.longestPath(node.left);
        let rightPath = this.longestPath(node.right);
        
        this.diameter = Math.max(this.diameter, leftPath + rightPath);
        
        return Math.max(leftPath, rightPath) + 1;
    }
}

Python solution

matched/original

class Solution:
    def __init__(self):
        self.diameter = 0
        
    def diameterOfBinaryTree(self, root):
        self.diameter = 0
        self.longestPath(root)
        return self.diameter
    
    def longestPath(self, node):
        if not node:
            return 0
        
        leftPath = self.longestPath(node.left)
        rightPath = self.longestPath(node.right)
        
        self.diameter = max(self.diameter, leftPath + rightPath)
        
        return max(leftPath, rightPath) + 1

Go solution

matched/original

package main

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

type Solution struct {
    diameter int
}

func (s *Solution) diameterOfBinaryTree(root *TreeNode) int {
    s.diameter = 0
    s.longestPath(root)
    return s.diameter
}

func (s *Solution) longestPath(node *TreeNode) int {
    if node == nil {
        return 0
    }
    
    leftPath := s.longestPath(node.Left)
    rightPath := s.longestPath(node.Right)
    
    s.diameter = max(s.diameter, leftPath + rightPath)
    
    return max(leftPath, rightPath) + 1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

Инициализируйте целочисленную переменную diameter для отслеживания самого длинного пути, найденного с помощью DFS.

Реализуйте рекурсивную функцию longestPath, которая принимает TreeNode в качестве входных данных и рекурсивно исследует дерево: Если узел равен None, вернуть 0. Рекурсивно исследовать левые и правые дочерние узлы, возвращая длины путей leftPath и rightPath. Если сумма leftPath и rightPath больше текущего diameter, обновить diameter. Вернуть большее из leftPath и rightPath плюс 1.

Вызвать longestPath с root.

😎