# Leetcode

```class Solution {
int maxx=INT_MIN;
public:

int ans(TreeNode* root)
{
if(root==NULL)return 0;
int l = ans(root->left);
int r = ans(root->right);
maxx = max(maxx,l+r+root->val);
return max(0,max(l+root->val,r+root->val));
}
int maxPathSum(TreeNode* root) {
int pathSum = ans(root);
return maxx;
}
};```
```class Solution {
int flag;
public:
int height(TreeNode* root)
{
if(root==NULL)return 0;
int hl = height(root->left);
int hr = height(root->right);
if(abs(hl-hr)>1)flag=1;
return 1+max(hl,hr);
}
bool isBalanced(TreeNode* root) {

int h = height(root);
if(flag)return false;
else return true;
}
};```
```class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
queue<TreeNode*> dq;
if(root)dq.push(root);
int flag = 0;
while(!dq.empty()){
vector<int> curlvl;
int size = dq.size();
// traverse all the nodes of current level
for(int s=0; s<size; s++){
root = dq.front(); dq.pop();
if(flag)
curlvl.insert(curlvl.begin(), root->val);
else
curlvl.push_back(root->val);
if(root->left)
dq.push(root->left);
if(root->right)
dq.push(root->right);
}
flag^=1;
ans.push_back(curlvl);
}
return ans;
}
};```
```class Solution {
public:
int vis[50001];
bool canReach(vector<int>& a, int i) {
if(i<0||i>=a.size()||vis[i])return false;
if(a[i]==0)return true;
vis[i]=1;
return canReach(a,i+a[i])||canReach(a,i-a[i]);
}
};```
```class Solution {
public:
vector<TreeNode*> inorder;
void inorderTraversal(TreeNode* root)
{
if(root==NULL)return ;
inorderTraversal(root->left);
inorder.push_back(root);
inorderTraversal(root->right);
}
TreeNode* build(int l,int r)
{
if(l>r)return NULL;
int mid = l+(r-l)/2;
TreeNode* root = inorder[mid];
root->left = build(l,mid-1);
root->right = build(mid+1,r);
return root;
}
TreeNode* balanceBST(TreeNode* root) {
if(root==NULL)return root;
inorderTraversal(root);
int n = inorder.size();
root = build(0,n-1);
return root;
}
};```