# Share my AVL tree based solution (Java)

• ``````public class Solution {
public class MyTreeNode extends TreeNode {
MyTreeNode(int x) {
super(x);
h = 1;  //height should be 1
}
int h;
MyTreeNode parent;
}
node.parent = null;
MyTreeNode root = node;
int val = 0;
MyTreeNode x = root;
while (runner != null) {
val = runner.val;
MyTreeNode z = new MyTreeNode(val);
x.right = z;
z.parent = x;
x = z;
runner = runner.next;
root = fixup(root,z);
}
return root;
}

public MyTreeNode fixup(MyTreeNode root, MyTreeNode z) {
MyTreeNode p;
p = z.parent;
while (p!=null) {
if (p.left==null) {
if (((MyTreeNode)(p.right)).h == 1) {
p.h = 2;
p = p.parent;
continue;
} else {
((MyTreeNode)p.right).parent = p.parent;
((MyTreeNode)p.right).left = p;
p.parent = (MyTreeNode)p.right;
p.h =1;
p.right = null;
if (p.parent.parent!=null)
p.parent.parent.right = p.parent;
if (p==root)
return p.parent;
else break;
}
} else {
if (Math.abs(((MyTreeNode)p.right).h-((MyTreeNode)p.left).h)<2) {
p.h++;
p = p.parent;
continue;
} else {
MyTreeNode temp = (MyTreeNode)((MyTreeNode)p.right).left;
((MyTreeNode)p.right).parent = p.parent;
((MyTreeNode)p.right).left = p;
p.parent = (MyTreeNode)p.right;
p.h --;
p.right = temp;
if (p.parent.parent!=null)
p.parent.parent.right = p.parent;
if (p==root)
return p.parent;
else break;
}
}
}
return root;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.