acash's blog

By acash, history, 5 months ago, In English,

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 = solve(root->left) + 1; int rightheight = solve(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

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by acash (previous revision, new revision, compare).

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do you call function "solve" from "diameterOfBinaryTree" and vice versa? It must work incorrect, as "diameterOfBinaryTree" function returns global maximum, not maximum for the corresponding subtree. Besides, you have two times more recursion depth.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Try: mx = max(mx, leftheight + rightheight — 2);

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

if root==NULL your solve has counted 1 for it already when passing solve(NULL)+1 instead of returning 0 ,return -1 if(root==NULL) and for leaf return 0 and get accepted :)