Welcome to Subscribe On Youtube
Java
-
/** 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. */ public class Diameter_of_Binary_Tree { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int max = 0; public int diameterOfBinaryTree(TreeNode root) { dfs(root); return max; } private int dfs(TreeNode root) { if (root == null) { return 0; } int leftDepth = dfs(root.left); int rightDepth = dfs(root.right); max = Math.max(max, leftDepth + rightDepth); return Math.max(leftDepth, rightDepth) + 1; } } }
-
// OJ: https://leetcode.com/problems/diameter-of-binary-tree/ // Time: O(N) // Space: O(H) class Solution { int ans = 0; int postorder(TreeNode *root) { if (!root) return 0; int left = postorder(root->left), right = postorder(root->right); ans = max(ans, left + right); return 1 + max(left, right); } public: int diameterOfBinaryTree(TreeNode* root) { postorder(root); return ans; } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def diameterOfBinaryTree(self, root: TreeNode) -> int: def dfs(root): if root is None: return 0 nonlocal ans left, right = dfs(root.left), dfs(root.right) ans = max(ans, left + right) return 1 + max(left, right) ans = 0 dfs(root) return ans ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def diameterOfBinaryTree(self, root): """ :type root: TreeNode :rtype: int """ self.ans = 0 def dfs(root): if not root: return 0 left = dfs(root.left) right = dfs(root.right) self.ans = max(self.ans, left + right) return max(left, right) + 1 dfs(root) return self.ans
Java
-
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int path; public int diameterOfBinaryTree(TreeNode root) { path = 1; depthFirstSearch(root); return path - 1; } public int depthFirstSearch(TreeNode node) { if (node == null) return 0; int leftDepth = depthFirstSearch(node.left); int rightDepth = depthFirstSearch(node.right); path = Math.max(path, leftDepth + rightDepth + 1); return Math.max(leftDepth, rightDepth) + 1; } }
-
// OJ: https://leetcode.com/problems/diameter-of-binary-tree/ // Time: O(N) // Space: O(H) class Solution { int ans = 0; int postorder(TreeNode *root) { if (!root) return 0; int left = postorder(root->left), right = postorder(root->right); ans = max(ans, left + right); return 1 + max(left, right); } public: int diameterOfBinaryTree(TreeNode* root) { postorder(root); return ans; } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def diameterOfBinaryTree(self, root: TreeNode) -> int: def dfs(root): if root is None: return 0 nonlocal ans left, right = dfs(root.left), dfs(root.right) ans = max(ans, left + right) return 1 + max(left, right) ans = 0 dfs(root) return ans ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def diameterOfBinaryTree(self, root): """ :type root: TreeNode :rtype: int """ self.ans = 0 def dfs(root): if not root: return 0 left = dfs(root.left) right = dfs(root.right) self.ans = max(self.ans, left + right) return max(left, right) + 1 dfs(root) return self.ans