二叉树上节点间的最大距离
1个回答
展开全部
从二叉树的节点A出发，可以向上或者向下走，但沿途的节点只能经过一次，当到达节点B时，路径上的节点数叫做A到B的距离
比如，下图所示的二叉树，节点4和节点2的距离为2，节点5和节点6的距离为5，给定一棵二叉树的头节点head，求整棵树上节点间的最大距离
1
2 3
4 5 6 7
如果二叉树的节点数为N，时间复杂度要求为O(N)
最大距离来自三种情况
1、h左子树上的最大距离
2、h右子树上的最大距离
3、h左子树上离h.left最远的距离（左子树高度）+h右子树上离h.right最远的距离（右子树高度）+1
比如，下图所示的二叉树，节点4和节点2的距离为2，节点5和节点6的距离为5，给定一棵二叉树的头节点head，求整棵树上节点间的最大距离
1
2 3
4 5 6 7
如果二叉树的节点数为N，时间复杂度要求为O(N)
最大距离来自三种情况
1、h左子树上的最大距离
2、h右子树上的最大距离
3、h左子树上离h.left最远的距离（左子树高度）+h右子树上离h.right最远的距离（右子树高度）+1
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
