问题描述

  1. 给定一颗二叉树，返回其直径
  2. https://leetcode-cn.com/problems/diameter-of-binary-tree/

收获

  1. 优化该问题的关键在于同时利用dfs的返回值以及在dfs过程中对一个全局变量进行设置这两种dfs的功能。
  2. 或者说在于对直径的理解
    • 我的理解是直径要么经过root，要么不经过root；经过root，直径就是左孩子的高度加右孩子的高度；不经过root，那么直径就是左孩子的直径，或者右孩子的直径。
    • 最优解法的理解是：直径是所有节点中，节点的左右孩子的高度之和最大的那个节点！转为求最大的左右孩子高度之和！直径=最大的左右孩子高度之和！