关键词：
来自于编程之美3.8。
参考：http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html 这里有比较详细的讨论！
题目：如果我们把二叉树看做图，父子节点之间的连线看成是双向的，我们姑且定义“距离”为两个节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。
如下图所示，树中相距最远的两个节点为A,B，最大距离为6。
书上对这个问题的分析是很清楚的，计算一个二叉树的最大距离有两个情况：
情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者
对于情况A来说，只需要知道左右子树的深度，然后加起来即可。
对于情况B来说，需要知道左子树的最远距离，右子树的最远距离。
只需要计算这两种情况的路径距离，并取其最大值，就是该二叉树的最大距离。
情况A 情况B
下面是书上的源码：
struct NODE
NODE* pLeft; // 左子树
NODE* pRight; // 右子树
int nMaxLeft; // 左子树中的最长距离
int nMaxRight; // 右子树中的最长距离
char chValue; // 该节点的值
;
int nMaxLen = 0;
// 寻找树中最长的两段距离
void FindMaxLen(NODE* pRoot)
// 遍历到叶子节点，返回
if (pRoot == NULL)
return;
// 如果左子树为空，那么该节点的左边最长距离为0
if (pRoot->pLeft == NULL)
pRoot->nMaxLeft = 0;
// 如果右子树为空，那么该节点的右边最长距离为0
if (pRoot->pRight == NULL)
pRoot->nMaxRight = 0;
// 如果左子树不为空，递归寻找左子树最长距离
if (pRoot->pLeft != NULL)
FindMaxLen(pRoot->pLeft);
// 如果右子树不为空，递归寻找右子树最长距离
if (pRoot->pRight != NULL)
FindMaxLen(pRoot->pRight);
// 计算左子树最长节点距离
if (pRoot->pLeft != NULL)
pRoot->nMaxLeft = ((pRoot->pLeft->nMaxLeft > pRoot->pLeft->nMaxRight) ? pRoot->pLeft->nMaxLeft : pRoot->pLeft->nMaxRight) + 1;
// 计算右子树最长节点距离
if (pRoot->pRight != NULL)
pRoot->nMaxRight = ((pRoot->pRight->nMaxLeft > pRoot->pRight->nMaxRight) ? pRoot->pRight->nMaxLeft : pRoot->pRight->nMaxRight)+1;
// 更新最长距离
if (pRoot->nMaxLeft + pRoot->nMaxRight > nMaxLen)
nMaxLen = pRoot->nMaxLeft + pRoot->nMaxRight;
以上代码得新定义一个Node类型，且代码比较复杂！
下面是精简版：
首先我们知道求二叉树的深度的代码是比较简单的，代码如下：
int DepthOfBinaryTree(BinaryTreeNode*pNode)
if (pNode==NULL)
return 0;
else //递归
return DepthOfBinaryTree(pNode->m_pLeft) > DepthOfBinaryTree(pNode->m_pRight) ?
DepthOfBinaryTree(pNode->m_pLeft) + 1 : DepthOfBinaryTree(pNode->m_pRight) + 1;
而我们要求的二叉树的最大距离其实就是求：肯定是某个节点左子树的高度加上右子树的高度加2，所以求出每个节点左子树和右子树的高度，取左右子树高度之和加2的最大值即可，假设空节点的高度为-1
代码如下：
//改进的版本
int HeightOfBinaryTree(BinaryTreeNode*pNode, int&nMaxDistance)
if (pNode == NULL)
return -1; //空节点的高度为-1
//递归
int nHeightOfLeftTree = HeightOfBinaryTree(pNode->m_pLeft, nMaxDistance) + 1; //左子树的的高度加1
int nHeightOfRightTree = HeightOfBinaryTree(pNode->m_pRight, nMaxDistance) + 1; //右子树的高度加1
int nDistance = nHeightOfLeftTree + nHeightOfRightTree; //距离等于左子树的高度加上右子树的高度+2
nMaxDistance = nMaxDistance > nDistance ? nMaxDistance : nDistance; //得到距离的最大值
return nHeightOfLeftTree > nHeightOfRightTree ? nHeightOfLeftTree : nHeightOfRightTree;
上面的函数的参数nMaxDistance返回的就是最大的距离，以下图作为测试。
输出如下：
注意：在数据结构与算法分析这本书上面，树的深度是不包括根节点的，树的深度就等于树的高度，所以上面的函数的返回值是能够代表树的深度，也就是高度的！所以在判断pNode==NULL的时候返回-1。
但是在剑指offer：面试题39，树的深度包括了根节点，所以在判断pNode==NULL的时候返回0。
如上图所示：按剑指offer上面的，深度为4，但是按数据结构与算法分析，深度则为3！这个需要特别注意。
算法题之求二叉树的最大距离
二叉树是一种非常经典的数据结构。如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。下面我们随意构... 查看详情
求二叉树中节点的最大距离
题目描写叙述假设我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义“距离”为两个节点之间的变数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。输入要求输入的第一行包括单独的一... 查看详情
二叉树内两个节点的最长距离(代码片段)
二叉树中两个节点的最长距离可能有三种情况：1.左子树的最大深度+右子树的最大深度为二叉树的最长距离2.左子树中的最长距离即为二叉树的最长距离3.右子树种的最长距离即为二叉树的最长距离因此，递归求解即可privatestaticc... 查看详情
关于数据结构
二叉树相关：定义，性点二叉树是一种树形结构，其特点是每个结点至多只有两颗子树，并且二叉树的子树有左右之分。非空二叉树叶子结点数等于度为2的结点的个数加1，即N0=N2+1非空二叉树上第K层上... 查看详情
3.二叉树的最大深度
题目：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的距离。/** *DefinitionofTreeNode: *classTreeNode{ *public: * intval; * TreeNode*left,*right;&nbs 查看详情
lintcode97.二叉树的最大深度
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的距离 样例给出一棵如下的二叉树:1/23/45这个二叉树的最大深度为3. /***DefinitionofTreeNode:*classTreeNode{*public:*intval;*TreeNode*left,*right;*TreeNode(intval){*this... 查看详情
104maximumdepthofbinarytree二叉树的最大深度
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶节点的最长路径上的节点数。案例：给出二叉树[3,9,20,null,null,15,7]， 3 /\ 9 20 / \ 15 7返回最大深度... 查看详情
二叉树上节点间的最大距离
参考技术A从二叉树的节点A出发，可以向上或者向下走，但沿途的节点只能经过一次，当到达节点B时，路径上的节点数叫做A到B的距离比如，下图所示的二叉树，节点4和节点2的距离为2，节点5和节点6的距离为5，给定一棵二叉树... 查看详情
算法系列——二叉树深度(代码片段)
...:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。思路题目很简单... 查看详情
算法系列——二叉树深度(代码片段)
...:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。思路题目很简单... 查看详情
算法系列——二叉树深度(代码片段)
...:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。思路题目很简单... 查看详情
二叉树9：二叉树的最大深度(代码片段)
本文主要分析两道题，LeetCode104如何找二叉树的最大深度和LeetCode559：N叉树的最大深度。1.LeetCode104二叉树的最大深度我们还是先看一下题意LeetCode104：给定一颗二叉树，找出其最大深度。二叉树的最大深度是根节... 查看详情
二叉树——高度和深度
...别，这里对代码随想录的内容做一个总结。详细内容看：二叉树的最大深度对于深度这个概念的理解基于力扣104.二叉树的最大深度题干的描述，二叉树的深度是指：二叉树的深度为根节点到最远叶子节点的最长路径上的节点数... 查看详情
ds二叉树—二叉树结点的最大距离(代码片段)
题目描述 二叉树两个结点的距离是一个结点经过双亲结点，祖先结点等中间结点到达另一个结点经过的分支数。二叉树结点的最大距离是所有结点间距离的最大值。例如，下图所示二叉树结点最大距离是3，C和D的距... 查看详情
leetcode练习(python)：树类：第104题：二叉树的最大深度：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明:叶子节点是指没有子节点
题目：二叉树的最大深度：给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明:叶子节点是指没有子节点的节点。思路：借助层序遍历来做，有多少层树就有多深。... 查看详情
lc二叉树的最大深度(代码片段)
LC二叉树的最大深度给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明:叶子节点是指没有子节点的节点。【代码】/***Definitionforabinarytreenode.*publicclassTreeNode*intval;*TreeNodelef... 查看详情
104.二叉树的最大深度(代码片段)
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例：给定二叉树 [3,9,20,null,null,15,7]，3/920/157返回它的最大深度 3。 ... 查看详情
104.二叉树的最大深度(代码片段)
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例：给定二叉树[3,9,20,null,null,15,7]，3/920/157返回它的最大深度 3。intmaxDepth(TreeN... 查看详情