Balanced Binary Tree
@VV_Driven n*log(n) is the mean Time complexity. and the worst comlexity is T(n)=T(n-1)+1...O(n^2)
I guess here -1 is a boolean marker, since the types of return value of two functions are different.
There is no one universal definition for balanced binary trees. In my answer above, I pointed out that AVL tree uses the same height-balanced definition as in this problem.
@nmbmlyx0211 Once the left sub-tree or right sub-tree is unbalance(the hight difference larger than 1), the corresponding value will be -1.
A good Intuitive and practical solution... better than above ones
if(root == null || isBalanced == false)
This will end unnecessary traversal.
your solution will do lots of useless searching.
What do you think is the traditional definition?
Have you tried? Puting the abs forward results 20ms, 16ms, and the original version results in 15ms, 16ms.
It's seems because the test cases are too weak...
No one has replied
After isBalancedTreeHelper(root->right,right) call gets complete, wouldn't values of left and right variables be same? Because left and right are alias to depth variable.
Is this solution O(n^2)?
@ash1625 Is the runtime O(n^2) in this case?
It's all the same to me ! haha
could you tell me why top - down solution is o(n^2) time complexity ?
my understanding is worst case would be linked list
then f(n) = o(n) + f(n-1) = o(n^2).
cgl1027. for this task yes. but there is another definition "every leaf should be away from root with difference no more than 1" which fails the testcase.
I think one recursive is better
Maybe to store the TreeNode's height into a HashMap is a better idea. That avoids calculating height of child nodes time and time again.
Disabled Categories are greyed out
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.