二叉树的直径
Problem statement:
问题陈述
Given a Binary Tree, find diameter of it. The diameter of a tree is the number of nodes on the longest path between two leaves in the tree.
给定二叉树找到它的直径 。 树的直径是树中两片叶子之间最长路径上的节点数。
Example:
例
For the above tree:Diameter is 7Longest paths:11->6->7->2->5->.9->45->6->7->2->5->9->4Both have 7 nodes
Solution:
解
Diameter of a tree
一棵树的直径
Diameter of a tree is number of nodes on the longest path between two leaves of tree.
树的直径是树的两片叶子之间最长路径上的节点数。
Now the fact is the longest path always passes through the root.
现在事实是最长的路径始终通过根。
In fact no of nodesheight of left subtree (there is the source/destination leaf node) height of right subtree(there is the destination/source leaf node) 1(for root)
实际上节点数左子树的高度(有源/目标叶节点)右子树的高度(有目标/源叶节点)1(对于根)
So actually the solution depends on finding the height of each subtree.
因此实际上解决方案取决于找到每个子树的高度。
Finding height of each subtree can be done using recursion or level order traversal. However, I prefer level order traversal (BFS rocks!)
可以使用递归或级别顺序遍历来找到每个子树的高度。 但是我更喜欢级别顺序遍历(BFS摇滚)
Algorithm:
算法
Diameterheight of left subtree height of right subtree1
直径左子树的高度右子树的高度1
Pre-requisite:
先决条件
A Queue q for level-order traversal, input binary tree, function to calculate height of subtrees
队列q用于级别顺序遍历输入二叉树用于计算子树的高度
FUNCTION height (root)1. Set h1;EnQueue (q, root);EnQueue (q, NULL);While(q is not empty)tempDeQueue(q) IF(temp is NULL)IF(q is not empty)EnQueue (q, NULL);h; //increment height as this is the end of the processed levelEnd IFELSEIF(temp->left)EnQueue (temp->left);IF(temp->right)EnQueue (temp->right);End IF-ELSEEnd While2. Return h; //height of the treeEnd FUNCTION
FUNCTION diameter (root)Return height (root->left) height(root->right) 1;End FUNCTION
C implementation
C 实现
#include using namespace std;// tree node is definedclass TreeNode{ public:int data;TreeNode *left;TreeNode *right;};// creating new node for treeTreeNode* newnode(int data) { TreeNode* node (TreeNode*)malloc(sizeof(TreeNode)); node->data data; node->left NULL; node->right NULL; return(node); } int height(TreeNode* node){int h1;queue q;Node* temp;q.push(node);q.push(NULL);while(!q.empty()){tempq.front();q.pop();if(!temp){if(!q.empty()){q.push(NULL);h;}}else{if(temp->left)q.push(temp->left);if(temp->right)q.push(temp->right);}}return h;}int diameter(TreeNode* node){if(nodeNULL)return 0;return height(node->left)height(node->right)1;}int main() { //**same tree is builted as shown in example**int k;cout<<"same tree is built as shown in example\n";TreeNode *rootnewnode(2); root->left newnode(7); root->right newnode(5); root->right->rightnewnode(9);root->right->right->leftnewnode(4);root->left->leftnewnode(2); root->left->rightnewnode(6);root->left->right->leftnewnode(5);root->left->right->rightnewnode(11);cout<<"Diameter of the tree is:\n"<
输出量
same tree is built as shown in exampleDiameter of the tree is:7
Example with explanation:
带有说明的示例
For our example treeCalculating height of left-subtreeRoot2;Root->left7Root->right5------------------------------------------height(7)h1root7Push 7Push NULLQueue status:7, NULL1st iterationQueue not emptyQueue front is 7Pop 7Push: 7->left(2) h2Push: NULLQueue status: 2, 6, NULL------------------------------------------3rd iterationQueue not emptyQueue front is 2Pop 2Push: Nothing ( 2->left (NULL) and 7->right (NULL) Queue status: 6, NULL------------------------------------------4th iterationQueue not emptyQueue front is 6Pop 6Push: 6->left (5) 6->right (11) Queue status: NULL, 5,11------------------------------------------5th iterationQueue not emptyQueue front is NULLPop NULLIncrement h//h3Push: NULLQueue status: 5, 11, NULL------------------------------------------6th iterationQueue not emptyQueue front is 5Pop 5Push: Nothing (5->left is NULL, 5->right is NULL)Queue status: 11, NULL------------------------------------------7th iterationQueue not emptyQueue front is 11Pop 11Push: Nothing (11->left is NULL, 11->right is NULL)Queue status: NULL------------------------------------------8th iterationQueue not emptyQueue front is NULLPop NULLQueue is emptySo no more pushing NULL------------------------------------------Queue is empty, hence endThus height of left subtree is 3Same way we can proceed to calculate right subtree height which is also 3Thus diameter of the tree is 3317
翻译自: https://www.includehelp.com/icp/diameter-of-binary-tree.aspx
二叉树的直径