二叉树上节点间的最大距离

发布网友发布时间：2023-01-07 11:57

共1个回答

热心网友时间：2023-10-20 04:36

从二叉树的节点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

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com