Q:
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:
Given a binary tree
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them.
A:
利用C++ 的参数reference type, 来完成 多个 返回值Given a binary tree
看helper( , int & maxDepth)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int diameterOfBinaryTree(TreeNode* root) { // use reference to get the modified value from other function int dummy=0; return helper(root, dummy); } private: int helper(TreeNode* root, int & maxDepth) // return the diameter of the tree { if(!root) { maxDepth = 0; return 0; } int leftDepth, rightDepth; int maxLeft = helper(root->left, leftDepth); int maxRight = helper(root->right, rightDepth); maxDepth = max(leftDepth, rightDepth) + 1; return max(maxLeft , max( maxRight, leftDepth + rightDepth) ); } };
No comments:
Post a Comment