Leetcode - 树

class Solution {
public:
    
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL) return true;
        if(p == NULL || q == NULL) return false;
        
        if(p->val != q->val) return false;
        bool left = isSameTree(p->left, q->left);
        bool right = isSameTree(p->right, q->right);
        return left&&right;
    }
};

class Solution {
public:
    
    bool isSymmetric(TreeNode* left, TreeNode* right){
        if(left == NULL || right == NULL)
            return left == right;
        if(right->val != left->val)
            return false;
        else
            return isSymmetric(left->right, right->left) && isSymmetric(left->left, right->right);
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)
            return true;
        else 
            return isSymmetric(root->left, root->right);
    }
};

class Solution {
public:
    int depthTravel(TreeNode* p, int depth){
        if(p == NULL) return depth;
        int l = depthTravel(p->left, depth+1);
        int r = depthTravel(p->right, depth+1);
        return r > l ? r : l;
    }
    int maxDepth(TreeNode* root) {  
        return depthTravel(root, 0);
    }
};

int height(TreeNode* p){
    return p == NULL ? 0 : max(height(p->left), height(p->right)) + 1;
}

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int d = 0;
        while(!q.empty()){
            d++;
            int size = q.size();
            for(int i=0; i<size; i++){
                TreeNode* cur = q.front();
                
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            
                q.pop();
                if(cur->left == cur->right) return d;
            }
        }
        return d;
    }
};

class Solution {
public:
    
    int height(TreeNode* p, int h){
        if(p == NULL) return h;
        int l = height(p->left, h+1);
        int r = height(p->right, h+1);
        return l > r ? l : r;
    }
      
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        return isBalanced(root->left) 
            && isBalanced(root->right) 
            && abs(height(root->left, 0) - height(root->right, 0)) <= 1;
    }
};

class Solution {
public:

    bool check(TreeNode* p, int sum, int target){
        if(p == NULL ) return false;
        if(p->left == p->right) return sum+p->val == target;
        return check(p->left, sum+p->val, target) || check(p->right, sum+p->val, target);
    }
    bool hasPathSum(TreeNode* root, int sum) {
        return check(root, 0, sum);
    }
};

class Solution {
public:
    
    void invert(TreeNode* p){
        if(p == NULL) return;
        TreeNode* t = p->left;
        p->left = p->right;
        p->right = t;
        
        invert(p->left);
        invert(p->right);
    }
    
    
    TreeNode* invertTree(TreeNode* root) {
        invert(root);
        return root;
    }
};

class Solution {
public:
    // 根节点一定是最小的值
    // 找到 比根大 但是比其他所有值小的
    
    int ret = -1;
    int minimum = ret;
    void compare(TreeNode* p){
        if(p == NULL ) return;
        if(p->val>minimum && (ret == -1 || p->val<ret)){
            ret = p->val;
        }
        compare(p->left);
        compare(p->right);
    }
    int findSecondMinimumValue(TreeNode* root) {
        if(root == NULL) return -1;
        minimum = root->val;
        compare(root);
        return ret;
    }
};

class Solution {
public:
    bool isSame(TreeNode* s, TreeNode* t){
        if(s == t) return true;
        if(!s || !t) return false;
        
        return s->val == t->val 
            && isSame(s->left, t->left)
            && isSame(s->right, t->right);
    }
   
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!t) return true;
        if(!s) return false;
                
        return (s->val == t->val ? isSame(s, t) : false)  
            || isSubtree(s->left, t) 
            || isSubtree(s->right, t);
    }
};

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while(root){
            if(root->val == val) return root;
            root = val > root->val ? root->right : root->left;
        }
        return NULL;
    }
};

class Solution {
public:
    
    TreeNode* getLeaf(stack<TreeNode* > &s){
        TreeNode* p = NULL;
        while(!s.empty()){
            p = s.top(); s.pop();
            
            if(p->right) s.push(p->right);
            if(p->left) s.push(p->left);
            
            if(p->left == p->right)
                return p;
        }
        return NULL;
    }
    
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        if(!root1 || !root2) return false;
        stack<TreeNode* > s1;
        stack<TreeNode* > s2;
        
        s1.push(root1); s2.push(root2);
        bool flag = true;
        
        TreeNode* p1;
        TreeNode* p2;
        
        while(flag && !s1.empty() && !s2.empty()){
            p1 = getLeaf(s1);
            p2 = getLeaf(s2);
            
            flag = p1->val == p2->val;
        }
        
        if(getLeaf(s1) || getLeaf(s2)) flag = false;
        
        return flag;
    }
};

class Solution {
public:
    int maxDepth(Node* root, int depth = 1) {
        if(!root) return depth-1;
        
        int m = depth;
        for(int i=0; i<root->children.size(); i++){
            int t = maxDepth(root->children[i], depth+1);
            m = m > t ? m : t;
        }
        
        return m;
    }
};

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> ret;
        queue<TreeNode* >* cur = new queue<TreeNode* >;
        queue<TreeNode* >* next = new queue<TreeNode* >;
        
        cur->push(root);
        
        double sum=0; int size=1;
        do{
            while(!cur->empty()){
                TreeNode* p = cur->front(); cur->pop();
                sum+=p->val;
                if(p->right) next->push(p->right);
                if(p->left) next->push(p->left);
            }
            ret.push_back(sum/size);
            sum=0; size = next->size();
            
            delete cur;
            cur = next;
            next = new queue<TreeNode* >;
        }while(!cur->empty());
        return ret;
    }
   
};

queue<TreeNode* > q;

q.push(root);
int cur = 1, next = 0;    

do{
    vector<int> v;
    int cnt = 0;
    while(cnt != cur){
        TreeNode* p = q.front(); q.pop();
        cnt++;

        // visit p

        if(p->left) {
            q.push(p->left);
            next++;
        }
        if(p->right) {
            q.push(p->right);
            next++;
        }

    }

    cur = next;
    next = 0;

    // deal with current level
}while(!q.empty());

class Solution {
public:

    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(!root) return NULL;
        
        if(low <= root->val && root->val <= high){      
            root->left = trimBST(root->left, low, high);
            root->right = trimBST(root->right, low, high);
            
        }else if(root->val < low){
            return trimBST(root->right, low, high);
        }else if(root->val > high){
            return trimBST(root->left, low, high);
        }
        

        return root;
    }
};

class Solution {
public:
    TreeNode* build(vector<int>& nums, int l, int r){
        if(l>=r) return NULL;
        if(l+1 == r) return new TreeNode(nums[l]);
        
        int mid = (l+r) >> 1;
        TreeNode* p = new TreeNode(nums[mid]);
        p->left = build(nums, l, mid);
        p->right = build(nums, mid+1, r);
        return p;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(nums, 0, nums.size());
    }
};

class Solution {
public:
    /**
    如果两个节点在一棵树的同一侧 那么同号
    */
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while ((root->val - p->val) * (root->val - q->val) > 0)
            root = p->val < root->val ? root->left : root->right;
        return root;
    }
};

class Solution {
public:
    //与当前节点最接近的节点应当是左子树的最右 右子树的最左
    
    int goAlongLeft(TreeNode* p){
        TreeNode* t = p;
        while(t->left) t=t->left;
        return t->val;
    }
    
    int goAlongRight(TreeNode* p){
        TreeNode* t = p;
        while(t->right) t=t->right;
        return t->val;
    }
    
    int _min = 0x7fffffff;
    int minDiffInBST(TreeNode* root) {
        if(!root) return _min;
        
        if(root->left) 
            _min = min(_min, abs(root->val - goAlongRight(root->left)));
        if(root->right) 
            _min = min(_min, abs(root->val - goAlongLeft(root->right)));
        
        minDiffInBST(root->left);
        minDiffInBST(root->right);
        return _min;
    }
};

class Solution {
public:  
    string tree2str(TreeNode* root){
        if(!root) return "";
        
        string t = to_string(root->val);
        
        if(root->left){
            t += '(' + tree2str(root->left) + ')';
        }else if(root->right){ // 没有左子树但是有右子树，就需要填补空白
            t += "()";
        }
        
        if(root->right){
            t += '(' + tree2str(root->right) + ')';
        }
        
        return t;
    }
};

class Solution {
public:
    /**
    额外空间
    */
    TreeNode h;
    TreeNode* head_p = &h;
    
    void travel(TreeNode* root){
        if(!root) return;
        
        travel(root->left);
        head_p->right = new TreeNode(root->val);
        head_p = head_p->right;
        travel(root->right);
    }
    
    TreeNode* increasingBST(TreeNode* root, TreeNode* tail = NULL) {
        travel(root);
        return h.right;
    }
};