//
// Created by EDZ on 2021/4/2.
//

#ifndef DIAMETEROFTREE_TREE_H
#define DIAMETEROFTREE_TREE_H
#include "deque"

//#ifndef max
//#define max(a, b) ((a) > (b) ? (a) : (b))
//#endif

template<class T>
T max(T a, T b) {
    return a > b ? a : b;
}

template<class T> class Node {
public:
    explicit Node(T val) {
        this->val = val;
        this->left = nullptr;
        this->right = nullptr;
    }
    Node *setLeft(Node *node) {this->left = node; return this;}
    Node *setRight(Node *node) {this->right = node; return this;}
    Node *getLeft() {return this->left;}
    Node *getRight() {return this->right;}
    T getValue() {return this->val;}
    static void preOrderTraverse(Node *node, void (*fn)(T)) {
        if (node == nullptr) {
            return;
        }
        fn(node->getValue());
        preOrderTraverse(node->left, fn);
        preOrderTraverse(node->right, fn);
    }
    static int maxDepth(Node *root) {
        if (root == nullptr) {return 0;}
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
    static int diameterOfBinaryTree(Node<T>* root) {
        if (root == nullptr) {return 0;}
        int ans = maxDepth(root->left) + maxDepth(root->right);
        return max(ans, max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)));
    }
    /**
     * 记录左子树的最大深度或者是右子树的最大深度
     * @param root
     * @param res
     * @return
     */
    static T helper(Node<T> *root, int &res) {
        if (!root) {return 0;}
        int left = helper(root->left, res);
        int right = helper(root->right, res);
        left = root->left ? left + 1 : left;
        right = root->right ? right + 1 : right;
        res = max(res, right + left);
        return max(left, right);
    }
private:
    Node *left;
    Node *right;
    T val;
};

template<class T> class Tree {
public:
    Tree() {this->root = nullptr;}
    explicit Tree(Node<T> *root) {this->root = root;}
    Node<T> *getRoot() {return this->root;}
    void preOrderTraverse(void (*fn)(T)) {
        Node<T>::preOrderTraverse(this->getRoot(), fn);
    }
    int maxDepth() {return Node<T>::maxDepth(this->root);}
    int diameterOfBinaryTree() {
        // return Node<T>::diameterOfBinaryTree(this->root);
        int ans = 0;
        Node<T>::helper(root, ans);
        return ans;
    }
    /**
     * 按层级遍历二叉树
     * https://blog.csdn.net/hansionz/article/details/81947834
     * https://blog.csdn.net/fareast_mzh/article/details/109709882
     * @param fn
     */
    void levelTraverse(void (*fn)(T)) {
        // 树为空，直接返回
        if (this->getRoot() == nullptr) {return;}
        std::deque<Node<T> *> q;
        // 先将根节点入队
        q.push_back(this->getRoot());
        Node<T> *front;
        Node<T> *left, *right;
        while (!q.empty()) {
            // 保存队头并访问, 出队
            front = q.front();
            fn(front->getValue());
            q.pop_front();
            // 将出队节点的左子树根入队
            left = front->getLeft();
            if (left != nullptr) {
                q.push_back(left);
            }
            // 将出队节点的右子树根入队
            right = front->getRight();
            if (right != nullptr) {
                q.push_back(right);
            }
        }
    }
private:
    Node<T> *root;
};

#endif //DIAMETEROFTREE_TREE_H

* main.cpp

#include <iostream>
#include "Tree.h"

int main() {
    auto *node = new Node<int>(1);
    node->setLeft((new Node<int>(2))
            ->setLeft(new Node<int>(4))
            ->setRight(new Node<int>(5)));
    node->setRight((new Node<int>(3)));
//            ->setLeft((new Node<int>(6))
//              ->setLeft(new Node<int>(8))
//              ->setRight(new Node<int>(9)))
//            ->setRight(new Node<int>(7)));

    Tree<int> t = Tree<int>(node);

    auto fn = [](int v) {std::cout << v << ",";};
    t.levelTraverse(fn);  // 按层级遍历
    std::cout << "\n";
    t.preOrderTraverse(fn); // 先序遍历
    std::cout <<"\n";
    // 二叉树的深度
    std::cout << "Depth=" << t.maxDepth() << "\n";
    // 二叉树的直径
    std::cout << "Diameter=" << t.diameterOfBinaryTree() <<"\n";

    return 0;
}

cmake_minimum_required(VERSION 3.17)
project(DiameterOfTree)

set(CMAKE_CXX_STANDARD 14)

add_executable(DiameterOfTree main.cpp Tree.h)

/**
 * 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)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) {    
    if (!root) {
        return 1;
    }
    var max = 0;
    var dfs = function(node) {
        if (!node) {return 0;}
        var lh = dfs(node.left);
        var rh = dfs(node.right);
        max = Math.max(max, lh + rh);
        return Math.max(lh, rh) + 1;
    } 
    dfs(root);
    return max;
};