Binary Tree - 二叉树最大宽度与最大距离
目录
1 问题描述
1.1 最大宽度
二叉树所有层中节点个数的最大值。例如下图二叉树最大宽度3，在第3层：
20 / \ 15 40 / \ \ 10 17 45 / / 8 43
1.2 最大距离
二叉树中节点距离是指两个节点之间边的个数。例如下图二叉树最大距离为9，节点对是100 和2600：
3000 / \ 1000 4000 / \ \ 600 1500 4800 / / \ 300 1300 2000 / \ 20 2500 \ / \ 100 2300 2800 / 2600
2 TODO 问题求解
2.1 最大宽度用树的广度遍历解决
2.2 最大距离是一个最优子结构问题的迭代
3 进一步问题
- 获取二叉树两个节点的距离
4 References
- leetcode
- https://leetcode.com/problems/maximum-width-of-binary-tree/description/
- Geeksforgeeks width
- https://www.geeksforgeeks.org/maximum-width-of-a-binary-tree/
- Geeksforgeeks maximum distance
- https://www.geeksforgeeks.org/find-distance-between-two-nodes-of-a-binary-tree/