Leetcode 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:
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.

Difficulty:Easy

Category:Tree

Solution

Solution 1: Recursion

Time complexity: O(n) Space complexity: O(n)

Runtime: 16 ms, faster than 99.52% of C++ online submissions for Diameter of Binary Tree. Memory Usage: 20.5 MB, less than 43.81% of C++ online submissions for Diameter of Binary Tree.

class Solution {
 public:
  int diameterOfBinaryTree(TreeNode* root) {
    int max_len = 0;
    dfs(root, max_len);
    return max_len;
  }

 private:
  int dfs(TreeNode* root, int& max_len) {
    if (!root) return 0;

    int left = dfs(root->left, max_len);
    int right = dfs(root->right, max_len);

    // Count the edge [left -> root] and [right -> root]
    max_len = max(max_len, left + right);
    return max(right, left) + 1;
  }
};

Solution 2: Iteration

Cite: LeetCode 543. Diameter of Binary Tree

Simulate recursion with a stack. We also need to track the return value of each node.

Time complexity: O(n) Space complexity: O(1)

Runtime: 20 ms, faster than 69.08% of C++ online submissions for Diameter of Binary Tree. Memory Usage: 20.8 MB, less than 8.09% of C++ online submissions for Diameter of Binary Tree.

class Solution {
 public:
  int diameterOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    int ans = 0;
    unordered_map<TreeNode*, int> d{{nullptr, -1}};
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
      TreeNode* node = s.top();
      if (d.count(node->left) && d.count(node->right)) {
        int l = d[node->left] + 1;
        int r = d[node->right] + 1;
        ans = max(ans, l + r);
        d[node] = max(l, r);
        // children's results will never be used again, safe to delete here.
        if (node->left) d.erase(node->left);
        if (node->right) d.erase(node->right);
        s.pop();
      } else {
        if (node->left) s.push(node->left);
        if (node->right) s.push(node->right);
      }
    }
    return ans;
  }
};
By guozetang            Updated: 2020-09-19 13:02:30

results matching ""

    No results matching ""