尽量每天至少一道算法题（leetCode刷题）

938. 二叉搜索树的范围和

理解题目：
1、二叉搜索树的特性是它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
2、此题是基于二叉树的中序遍历

• 非递归算法，利用栈的特性

int rangeSumBST(TreeNode* root, int L, int R) {
        if(root == NULL){
            return 0;
        }
        int summary = 0;
        stack<TreeNode*> s;
        TreeNode *curNode = root;
        while(!(s.empty()) || curNode != NULL){
            while (curNode != NULL) {
                s.push(curNode);
                curNode = curNode->left;
            }

            curNode = s.top();
            s.pop();
            if (curNode->val >= L && curNode->val <= R) {
                summary += curNode->val;
            }
            curNode = curNode->right;
        }

        return summary;
    }

• 递归算法

int rangeSumBST(TreeNode* root, int L, int R) {
        if(root->val < L){
            return rangeSumBST(root->right,L,R);
        }else if(root->val > R){
            return rangeSumBST(root->left,L,R);
        }else{
           return root->val + rangeSumBST(root->right,L,R) + rangeSumBST(root->left,L,R);
        }
    }

1021. 删除最外层的括号

方法一：

 string removeOuterParentheses(string S) {
        if (S.empty()) {
            return "";
        }
        stack<char> st;
        string result;
        int start = 0;
        int end = 0;
        for (int i=0; i < S.size(); i++) {
            char c = S[I];
            if (c == '(') {
                if (st.empty()) {
                    start = I;
                }
                st.push(c);
            }else if (c == ')'){
                st.pop();
                if (st.empty()) {
                    end = I;
                }
            }
            if (st.empty()) {
                string sub = S.substr(start + 1,end - start - 1);
                result += sub;
            }
        }
        return result;
    }

方法二：

   string removeOuterParentheses(string S) {
        if (S.empty()) {
            return "";
        }
        
        string result;
        int l = 0;
        int r = 0;
        for (int i = 1; i < S.size(); i ++) {
            if (S[i] == '(') {
                l++;
            }else{
                r++;
            }

            if (l >= r) {
                result.push_back(S[I]);
            }else{
                I++;
                l = r = 0;
            }
        }
        return result;
    }

617. 合并二叉树

 TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL && t2 == NULL) {
            return NULL;
        }else if (t1 != NULL && t2 == NULL) {
            return t1;
        }else if (t1 == NULL && t2 != NULL) {
            return t2;
        }else{
            t1->val += t2->val;
            t1->left = mergeTrees(t1->left, t2->left);
            t1->right = mergeTrees(t1->right, t2->right);
            return t1;
        }
    }

WechatIMG2204.png WechatIMG2205.png

从上图可看出，==操作比！操作耗时。

136. 只出现一次的数字

做这道题时，为了降低时耗，在一开始就用一个变量来记录数组的长度，而不是在每次for循环时都去调用nums.size()，所以平时写代码时，要养成这种良好的代码风格。

   class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int count = nums.size();
        int temp = 0;
       if (count == 0) {
            return temp;
        }
        
        for (int i = 0; i < count; i++) {
            temp ^= nums[i];
        }
        return temp;
    }
};

461. 汉明距离

1、这道题答案很值得细细品味，思路走出了宏观，进入到计算机的微观世界（所有的符号到了计算机底层都转换成01二进制。
2、利用二进制异或特性来找出两个数对应二进制不同位，再运用不断移位并且与1按位与来计算二进制中1的个数。

class Solution {
public:
    int hammingDistance(int x, int y) {
        int temp = x^y;
        int count = 0;
        while (temp != 0) {
            if ((temp&1) == 1) {
                count++;
            }
            temp = temp >>1;
        }
        return count;
    }
};