Share my AVL tree based solution (Java)


  • 0
    K
    public class Solution {
        public class MyTreeNode extends TreeNode {
            MyTreeNode(int x) {
    			super(x);
    			h = 1;  //height should be 1
    		}
    		int h;
            MyTreeNode parent;
        }
        public TreeNode sortedListToBST(ListNode head) {
            if (head==null) return null;
            MyTreeNode node = new MyTreeNode(head.val);
            node.parent = null;
            MyTreeNode root = node;
            ListNode runner = head.next;
            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;
        }
    }

Log in to reply
 

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