[LeetCode] 543. Diameter of Binary Tree

轉自LeetCode

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 longestpath 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.

<Solution>

想法如下

• 歷遍整個樹，把每個 node 都當做 root，那麼以此 node 為 root 的最長 path 就會是 左子樹深度 + 右子樹深度

• 過程中，記錄最長的 path，最後就是答案

code如下

C++

	/**
	* 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 ans = 0;
	int diameterOfBinaryTree(TreeNode* root) {
	dfs(root);
	return ans;
	}
	int dfs(TreeNode *root) {
	if(!root) {
	return 0;
	}
	int leftDepth = dfs(root->left);
	int rightDepth = dfs(root->right);
	//>> calcualte the max depth
	ans = max(ans, leftDepth + rightDepth);
	//>> return depth
	return max(leftDepth, rightDepth) + 1;
	}
	};

view raw diameterOfBinaryTree.cpp hosted with ❤ by GitHub