543. Tree diameter

543_solution1_recursive.c

#include "tree_node.h"

static int height(struct TreeNode *node, int *best) {
  if (!node)
    return 0;

  int l = height(node->left, best);
  int r = height(node->right, best);

  if (l + r > *best)
    *best = l + r;
  return 1 + (l > r ? l : r);
}

int diameterOfBinaryTree(struct TreeNode *root) {
  int best = 0;
  height(root, &best);
  return best;
}

tree_node.h

#pragma once

#include <stddef.h>

// Definition for a binary tree node.
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

543_solution1_recursive.cpp

#include "tree_node.h"
#include <algorithm>

using namespace std;

class Solution {
public:
  int diameterOfBinaryTree(TreeNode *root) {
    int best = 0;
    height(root, best);
    return best;
  }

private:
  int height(TreeNode *node, int &best) {
    if (!node)
      return 0;

    int l = height(node->left, best);
    int r = height(node->right, best);

    best = max(best, l + r);
    return 1 + max(l, r);
  }
};

tree_node.h

#pragma once

// Definition for a binary tree node.
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

543_solution1_recursive.go

package trees

func diameterOfBinaryTree(root *TreeNode) int {
    best := 0

    var height func(node *TreeNode) int
    height = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        l := height(node.Left)
        r := height(node.Right)

        best = max(best, l+r)
        return 1 + max(l, r)
    }

    height(root)
    return best
}

tree_node.go

package trees

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

543_solution1_recursive.java

class Solution {
    private int best;

    public int diameterOfBinaryTree(TreeNode root) {
        best = 0;
        height(root);
        return best;
    }

    private int height(TreeNode node) {
        if (node == null)
            return 0;

        int l = height(node.left);
        int r = height(node.right);

        best = Math.max(best, l + r);
        return 1 + Math.max(l, r);
    }
}

TreeNode.java

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

543_solution1_recursive.js

const TreeNode = require("./tree_node");

var diameterOfBinaryTree = function (root) {
  let best = 0;

  const height = (node) => {
    if (!node) return 0;

    const l = height(node.left);
    const r = height(node.right);

    best = Math.max(best, l + r);
    return 1 + Math.max(l, r);
  };

  height(root);
  return best;
};

tree_node.js

// Definition for a binary tree node.
function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

module.exports = TreeNode;

543_solution1_recursive.py

from typing import Optional

from tree_node import TreeNode


class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        best = 0

        def height(node: Optional[TreeNode]) -> int:
            nonlocal best
            if not node:
                return 0

            l = height(node.left)
            r = height(node.right)

            best = max(best, l + r)
            return 1 + max(l, r)

        height(root)
        return best

tree_node.py

# 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

543_solution1_recursive.rs

use std::cell::RefCell;
use std::rc::Rc;

use crate::tree_node::TreeNode;

impl Solution {
    pub fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut best = 0;
        Self::height(&root, &mut best);
        best
    }

    fn height(node: &Option<Rc<RefCell<TreeNode>>>, best: &mut i32) -> i32 {
        match node {
            None => 0,
            Some(n) => {
                let n = n.borrow();
                let l = Self::height(&n.left, best);
                let r = Self::height(&n.right, best);

                *best = (*best).max(l + r);
                1 + l.max(r)
            }
        }
    }
}

tree_node.rs

use std::cell::RefCell;
use std::rc::Rc;

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}