7.9 construct biT还少一道

to do

1] Balanced Binary Tree

注意剪枝更efficient，比trivial的recursion快。

MARK: redo W/ iterative

public:
    bool isBalanced(TreeNode* root) {
        return balancedDepth(root)!=-1;
    }
private:
    // return -1 if not balanced, or the depth
    int balancedDepth(TreeNode* root) {
        if (!root) return 0;
        int dl = balancedDepth(root->left);
        int dr = balancedDepth(root->right);
        if (dl<0 || dr<0 || abs(dl-dr)>1) return -1; //trim the tree!
        return 1+max(dl, dr);
    }

2] Flatten Binary Tree to Linked List

一开始没写check last， segfault

    void flatten(TreeNode* root) {
        if (!root) return;
        flatten(root->left);
        flatten(root->right);
        
        TreeNode* last= root->left;
        while (last && last->right) { last = last->right; } //note check if last exists !!
        if (last) {
            last->right = root->right;
            root->right = root->left;
            root->left = nullptr;
        }
    }

3.1] Populating Next Right Pointers in Each Node

no problem using queue, but not const memo and note

queue: pop front, push back

• method 1: recursion, not really constant space

    void connect(TreeLinkNode *root) {
        if (!root) return;
        connect(root->left);
        connect(root->right);
        
        TreeLinkNode* l=root->left, *r=root->right;
        while (l) {
            l->next=r;
            l=l->right;
            r=r->left;
        }
    }

• method 2
  while loop中还可以归纳，可是这样很清楚诶。。

    void connect(TreeLinkNode *root) {
        if (!root) return;
        TreeLinkNode* top = root;
        while (1) {
            TreeLinkNode* leftMost = top->left;
            if (!leftMost) return;
            TreeLinkNode* bottom = leftMost;
            while (top) {
                if (bottom != top->left) {
                    bottom->next=top->left;
                    bottom = bottom->next;
                } 
                bottom->next = top->right;
                bottom = bottom->next;
                top = top->next;
            }
            top = leftMost;
        }
    }

3.2] btw Binary Tree Right Side View

同样以上办法解决此题, or better: modified pre-order!

    void rightR(TreeNode* root, int level, vector<int>& v) {
        if (!root) return;
        if (v.size()<level) 
            v.push_back(root->val);
        if (root->right) rightR(root->right, level+1, v);
        if (root->left) rightR(root->left, level+1, v);
    }
    vector<int> rightSideView(TreeNode* root) {
        vector<int> v;
        rightR(root, 1, v);
        return v;
    }

3.2] Populating Next Right Pointers in Each Node II

hard, rethink! mark to redo

    void connect(TreeLinkNode *root) {
        if (!root) return;
        TreeLinkNode dummy(-1);
        for (TreeLinkNode* top=root, *bottom=&dummy; top; top=top->next) {
            if (top->left){
                bottom->next = top->left;
                bottom = bottom->next;
            }
            if (top->right){
                bottom->next = top->right;
                bottom = bottom->next;
            }
        }
        connect(dummy.next);
    }

4] Construct Binary Tree from Preorder and Inorder Traversal

再写吧，重构思

An InputIterator
is an Iterator that can read from the pointed-to element. InputIterator
s only guarantee validity for single pass algorithms: once an InputIterator
i has been incremented, all copies of its previous value may be invalidated.

    template<typename InputIterator>
    TreeNode* buildR(InputIterator p1, InputIterator p2, InputIterator i1, InputIterator i2) {
        if (p1>p2 || i1>i2) return nullptr;
        TreeNode* root = new TreeNode(*p1);
        int index = distance(i1, find(i1, i2, root->val));
        root->left = buildR(p1+1, p1+index, i1, i1+index-1);
        root->right = buildR(p1+index+1, p2, i1+index+1, i2);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty()) return nullptr;
        return buildR(preorder.begin(), preorder.end()-1, inorder.begin(), inorder.end()-1);
    }