| by YoungTimes | No comments

数据结构与算法-计算二叉树中节点的最大距离

1.问题定义

如果把二叉树看做无向图,我们姑且定义二叉树的“距离”为节点之间边的个数。现在要计算二叉树中相距最远的两个节点之间的距离。

数据结构与算法-计算二叉树中节点的最大距离

二叉树的节点距离计算有几种情况:

1) 根节点为空,路径长度为0;

2) 根节点非空的情况下,分为两种情况:

情况A: 路径经过左子树的最深节点,通过根节点,再到右子树的最深节点。

情况B: 路径不穿过根节点,而是左子树或右子树的最大距离路径,取其大者。

只需要计算这两个情况的路径距离,并取其大者,就是该二叉树的最大距离。

数据结构与算法-计算二叉树中节点的最大距离

2.代码实现(c++版本)

int MaxDistance(TreeNode* node, int& max_left, int& max_right) {
  max_left = 0;
  max_right = 0;
  if (node == nullptr) {
      return 0;
  }

  int max_dist_left = 0;
  int max_left_left = 0;
  int max_left_right = 0;
  int max_dist_right = 0;
  int max_right_left = 0;
  int max_right_right = 0;

  if (node->left != nullptr) {
    max_dist_left = MaxDistance(node->left, max_left_left, max_left_right);
    max_left = std::max(max_left_left, max_left_right) + 1;
  }

  if (node->right != nullptr) {
    max_dist_right = MaxDistance(node->right, max_right_left, max_right_right);
    max_right = std::max(max_right_left, max_right_right) + 1;
  }

  return std::max(std::max(max_dist_left, max_dist_right), max_left + max_right);
}

发表评论