二叉树直径 [英] Diameter of Binary Tree

问题描述

树的直径(有时称为宽度)是树中任何两个节点之间最长路径上的节点数".

"The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between any two nodes in the tree".

下面的C ++函数在所有情况下都能找到二叉树的直径吗?称为s=0，并且root =二叉树的根

Will the C++ function below works for all cases to find the diameter of a binary tree? Called as s=0, and root = root of the binary tree

int helper(node *root,int &s){

  int l = 0, r = 0;

  if(root == NULL){
     return 0; 
  }
  l= helper(root->left,s);  //height of left subtree.
  r= helper(root->right,s); //height of right subtree.

  int mx_single=max(l,r)+1;
  int mx_top=max(mx_single,l+r+1);
  s=max(s,mx_top);
  return mx_single;
}

返回主目录后，ans将为s.

推荐答案

在很多情况下，这对我来说似乎是错误的，但是如果您的变量名更具描述性，那将很有帮助.该函数需要返回指定树的直径，但是递归实现还需要使用每个子树的高度.

It looks wrong to me for many cases, but it would be helpful if your variable names were more descriptive. The function needs to return the diameter of the specified tree, but the recursive implementation also needs to use the height of each sub-tree.

根据直径的定义，将叶子节点包括在计数中，可以像下面这样递归地重新构造它:

Taking your definition of diameter to include the leaf nodes in the count, it can be reformulated recursively like so:

• 如果树由单个节点组成，则其直径为1.(整棵树是从一个叶节点到其自身的单节点路径).

• if the tree consists of a single node, then its diameter is 1. (The whole tree is a single-node path from one leaf node to itself).

如果子树的根节点恰好有一个子节点，则其直径为以该子节点为根的子树的直径.这是因为所有叶子节点都在子树中，因此从叶子到叶子的所有非循环路径都被限制在子树中.

if the root node of the sub-tree has exactly one child then its diameter is the diameter of the sub-tree rooted at that child. That follows because all the leaf nodes are in the subtree, therefore all the acyclic paths from leaf to leaf are confined to the subtree.

否则，直径是左子树的直径，右子树的直径以及两个子树的高度之和(以节点为单位)中最大的.这考虑了最长的叶到叶路径包含在左侧子树中，包含在右侧子树中或通过根的可能性.在后一种情况下，您无需确定实际路径；子树的高度告诉您它有多长(根+ 1个节点).

otherwise, the diameter is the greatest among the diameter of the left subtree, the diameter of the right subtree, and one plus the sum of the heights of the two subtrees (measured in nodes). This considers the possibilities that the longest leaf-to-leaf path is contained in the left subtree, is contained in the right subtree, or passes through the root. In the last case you don't need to identify the actual path; the subtree heights tell you how long it is (+ 1 node for the root).

接收子树的高度以处理第三个替代方法似乎是程序中参数s的目的，但您从未使用.

Receiving the sub-tree heights to handle the third alternative appears to be the purpose of parameter s in your program, but you don't ever use it.

您的程序将为各种各样的树木返回错误的结果

Your program will return the wrong result for a wide variety of trees, among them

  N
 /
1

(直径1，但您的函数将返回2)

(diameter 1, but your function will return 2)

  2
 / \
1   3

(直径3，但您的函数将返回2)

(diameter 3, but your function will return 2)

  3
 / \
2   4
 \
  1

(直径4，但您的函数将返回3)

(diameter 4, but your function will return 3)

  N
 / \
N   4
   / \
  3   5
 /   /
2   6
 \   \
  1   7

(直径7，但您的函数将返回5)

(diameter 7, but your function will return 5)

[在每个图中，沿用于测量树径的路径上的节点均已编号，所有其他节点均指定为'N'.]

[In each figure, nodes along a path that measures the tree diameter are numbered, and all other nodes are designated 'N'.]

实际上，您的函数会返回 height (以节点数而不是直径计).在有利的情况下，它似乎可以在s中记录直径，但不一致.

In fact, your function returns the height, counted in nodes, not the diameter. It looks like under favorable circumstances it may record the diameter in s, but not consistently.

这篇关于二叉树直径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！