Day 115, #229, Majority Element II, Kth Smallest Element in a BST

Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Hint:

1. How many majority elements could it possibly have?

---------------------------------------
注意for loop里的判断

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> rt;
        if (nums.size() == 0) return rt;
        
        int num1 = 0, num2 = 0, count1 = 0, count2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (count1 == 0 && (count2 == 0 || nums[i] != num2)) {
                num1 = nums[i];
                count1++;
            }else if (count2 == 0 && nums[i] != num1){
             count2++;
             num2 = nums[i];
            }else if (nums[i] == num1) {
                count1++;
            }else if (nums[i] == num2) {
                count2++;
            }else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == num1) count1++;
            else if (nums[i] == num2) count2++;
        }
        if (count1 * 3 > nums.size()) rt.push_back(num1);
        if (count2 * 3 > nums.size()) rt.push_back(num2);
        return rt;
    }
};

Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

-------------------------------------------------------------------------------
COME BACK for the follow up

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void preorder(TreeNode* root, int &k, TreeNode *&kth) {
        if (root == NULL) return;
        preorder(root->left,k,kth);
        k--;
        if (k == 0) kth = root;
        else preorder(root->right,k,kth);
    }

    int kthSmallest(TreeNode* root, int k) {
        TreeNode *kth = NULL;
        preorder(root,k,kth);
        return kth->val;
    }
};

另一种做法，找出子树的数量 updated on Jan-4th-2019

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode rt = null;
    public int kthSmallest(TreeNode root, int k) {
        dfs(root, k);
        return rt.val;
    }
    
    private int dfs(TreeNode root, int k) {
        if (root == null) return 0;
        int l = dfs(root.left, k);
        
        if (l + 1 == k) {
            rt = root;
        }
        
        int r = dfs(root.right, k - l - 1);
        return l + r + 1;
    }
}

Follow up
修改TreeNode结构，加入count。O(n)重建树，O(lg n) 找到Kth smallest