Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Urgent help for interview

Revision en1, by acash, 2019-07-04 17:20:01

Please help : I have two job interview first one is tomorrow next one is a week later In last 18 hours i solved 25 interview problems from diferent In seven days My target is 300 ,please save my life :)

I am trying to find diameter using recursion ,I am confused with recursion

some of the test cases I tried I got correct answer at some point Integer overflow occured But Below author's solution was accepted with same data types

My approach:

For every node, length of longest path which pass it = MaxDepth of its left subtree + MaxDepth of its right subtree.

My question is whats wrong with my implementation


class Solution { public: int mx = 0; int solve(TreeNode* root) { if (root == NULL)return 0; int leftheight = diameterOfBinaryTree(root->left) + 1; int rightheight = diameterOfBinaryTree(root->right) + 1; mx = max(mx, leftheight + rightheight); return max(leftheight, rightheight); } int diameterOfBinaryTree(TreeNode* root) { solve(root); return mx; } };

Authors approach: same approach but different recursion implementation

  class Solution {
  public:
      int maxdiadepth = 0;

      int dfs(TreeNode* root) {
          if (root == NULL) return 0;

          int leftdepth = dfs(root->left);
          int rightdepth = dfs(root->right);

          if (leftdepth + rightdepth > maxdiadepth) maxdiadepth = leftdepth + rightdepth;
          return max(leftdepth + 1, rightdepth + 1);
      }

      int diameterOfBinaryTree(TreeNode* root) {
          dfs(root);

          return maxdiadepth;
      }
  };

Problem link

Tags leetcode, #interview

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English acash 2019-07-04 17:33:08 46
en1 English acash 2019-07-04 17:20:01 1824 Initial revision (published)