class Solution {

public:

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        if ((root -> val > p -> val) && (root -> val > q -> val)) {

            return lowestCommonAncestor(root -> left, p, q);

        }

        if ((root -> val < p -> val) && (root -> val < q -> val)) {

            return lowestCommonAncestor(root -> right, p, q);

        }

        return root;

    }

};

/////////////////////////////////

class Solution {

public:

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        TreeNode* cur = root;

        while (true) {

            if ((cur -> val > p -> val) && (cur -> val > q -> val)) {

                cur = cur -> left;

            } else if ((cur -> val < p -> val) && (cur -> val < q -> val)) {

                cur = cur -> right;

            } else {

                return cur;

            }

        }

    }

};

void binaryTreePaths(vector<string>& result, TreeNode* root, string t) {

    if(!root->left && !root->right) {

        result.push_back(t);

        return;

    }

    if(root->left) binaryTreePaths(result, root->left, t + "->" + to_string(root->left->val));

    if(root->right) binaryTreePaths(result, root->right, t + "->" + to_string(root->right->val));

}

vector<string> binaryTreePaths(TreeNode* root) {

    vector<string> result;

    if(!root) return result;

    binaryTreePaths(result, root, to_string(root->val));

    return result;

}

Iteration method

  class Solution(object):

  def addDigits(self, num):

    """

    :type num: int

    :rtype: int

    """

    while(num >= 10):

        temp = 0

        while(num > 0):

            temp += num % 10

            num /= 10

        num = temp

    return num

Digital Root

this method depends on the truth:

N=(a[0] * 1 + a[1] * 10 + ...a[n] * 10 ^n),and a[0]...a[n] are all between [0,9]

we set M = a[0] + a[1] + ..a[n]

and another truth is that:

1 % 9 = 1

10 % 9 = 1

100 % 9 = 1

so N % 9 = a[0] + a[1] + ..a[n]

means N % 9 = M

so N = M (% 9)

as 9 % 9 = 0,so we can make (n - 1) % 9 + 1 to help us solve the problem when n is 9.as N is 9, ( 9 - 1) % 9 + 1 = 9


///就是一个数的数根等于该数各位数的和的mod 9
///  (num-1)%9+1  等于 num%9，这为了解决9的树根时9而不是0的问题

class Solution(object):

def addDigits(self, num):

    """

    :type num: int

    :rtype: int

    """

    if num == 0 : return 0

    else:return (num - 1) % 9 + 1

bool isUgly(int num) {

    if(num == ) return false;

    while(num% == ) num/=;

    while(num% == ) num/=;

    while(num% == ) num/=;

    return num == ;

}

1.XOR
相同则为0。num[]的数字和下标一样

public int missingNumber(int[] nums) { //xor

    int res = nums.length;

    for(int i=0; i<nums.length; i++){

        res ^= i;

        res ^= nums[i];

    }

    return res;

}

2.SUM

public int missingNumber(int[] nums) { //sum

    int len = nums.length;

    int sum = (0+len)*(len+1)/2;

    for(int i=0; i<len; i++)

        sum-=nums[i];

    return sum;

}

3.Binary Search

public int missingNumber(int[] nums) { //binary search

    Arrays.sort(nums);

    int left = 0, right = nums.length, mid= (left + right)/2;

    while(left<right){

        mid = (left + right)/2;

        if(nums[mid]>mid) right = mid;

        else left = mid+1;

    }

    return left;

}

Summary:

If the array is in order, I prefer Binary Search method. Otherwise, the XOR method is better.

283. Move Zeroes

class Solution {

public:

    void moveZeroes(vector<int>& nums) {

        int j = ;

        // move all the nonzero elements advance

        for (int i = ; i < nums.size(); i++) {

            if (nums[i] != ) {

                nums[j++] = nums[i];

            }

        }

        for (;j < nums.size(); j++) {

            nums[j] = ;

        }

    }

};

bool wordPattern(string pattern, string str) {

    map<char, int> p2i;

    map<string, int> w2i;

    istringstream in(str);

    int i = , n = pattern.size();

    for (string word; in >> word; ++i) {

        if (i == n || p2i[pattern[i]] != w2i[word])

            return false;

        p2i[pattern[i]] = w2i[word] = i + ;

    }

    return i == n;

}