Simple and esay understood c++ code based on balanced Binary Tree(AVL)


  • 0
    X

    balance the -2 and -1 node everytime

    class Solution {
    struct record{
        TreeNode *node;
        int disHeight;
        record(TreeNode *arg) : node(arg), disHeight(0){};
    };
    public:
        TreeNode *sortedListToBST(ListNode *head) {
            if(!head)
                return NULL;
            //initial construct
            vector<record> rightLine;
            TreeNode *node = new TreeNode(head->val);
            record tmp(node);
            rightLine.push_back(tmp);
            head = head->next;
            //loop and AVL balance
            while(head != NULL){
                TreeNode *node = new TreeNode(head->val);
                rightLine[rightLine.size()-1].node->right = node;
                record tmp(node);
                for(int i=rightLine.size()-1; i>=0; i--){
                    if(--rightLine[i].disHeight == -2){
                        rightLine[i].node->right = rightLine[i+1].node->left;
                        rightLine[i+1].node->left = rightLine[i].node;
                        rightLine[i+1].disHeight = 0;
                        if(i != 0)
                            rightLine[i-1].node->right = rightLine[i+1].node;
                        rightLine.erase(rightLine.begin() + i);
                        break;
                    }
                }
                rightLine.push_back(tmp);
                head = head->next;
            }
            return rightLine[0].node;
        }
    };

Log in to reply
 

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