//
// Created by Mr.Hu on 2018/12/15.
//
// leetcode 543 diameter of binary tree
//
// 题目给定二叉树,要求得到该二叉树的直径(所谓直径,就是二叉树所有节点中,两个节点件距离最长的情况)
//
// 要想求每个经过每个节点的路径长度,其实就是求该节点左右子树的最长路径树,而求左右子树最长路径,可以利用DFS的思想,
// 遍历得到左子树中最长的情况,同时利用相同的方法,遍历得到右子树中最长的情况,两个相加即可得到经过该节点最长的路径;
// 对树中所有节点进行想用的操作,然后每次比较取当前做长路径,最后输出即可。
//
// 但是上述方法只超过了百分之十五的方案。不难发现,我们在计算每个节点路径时,从上到下进行计算,其实对于下面的节点来说,递归操作重复计算了很多次,
// 我们也可以使用额外的存储空间,从底向上来进行计算,保留每个节点的路径左右子树的路径长度,这样可以大大节省时间。
//
1 |
|