543.Diameter of Binary Tree
Given a binary tree,you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the?longest?path between any two nodes in a tree. This path may or may not pass through the root. Example: 1 / 2 3 / 4 5 Return?3,which is the length of the path [4,2,1,3] or [5,3]. Note:?The length of path between two nodes is represented by the number of edges between them. 思路:其实所谓的二叉树的“直径”其实就是节点左右子树的最大深度和,而现在需要求出这个和的最大值。在递归求二叉树的深度时,记录下当前每个节点的深度,比较出最大值即可。 1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x),left(NULL),right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 int diameterOfBinaryTree(TreeNode* root) 13 { 14 res = 1; 15 treeDepth(root); 16 return res - 1; 17 } 18 int treeDepth(TreeNode* node) 19 { 20 if(node == nullptr) 21 return 0; 22 int L = treeDepth(node->left); 23 int R = treeDepth(node->right); 24 res = max(res,L+R+1); 25 return max(L,R)+1; 26 } 27 private: 28 int res; 29 }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |