Yanyg - SAN Software Engineer

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