1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int, int>> v;
        for (int i=0; i<nums.size(); i++) {
            v.push_back({nums[i], i});
        }
        std::sort(v.begin(), v.end());
        int l = 0, r = nums.size()-1;
        vector<int> res;
        while (l < r) {
            int sum = v[l].first + v[r].first;
            if(sum == target) {
                res.push_back(v[l].second);
                res.push_back(v[r].second);
                break;
            }
            else if(sum < target) l++;
            else r--;
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    bool judgeSquareSum(int c) {
        long a = 0, b = sqrt(c);
        while (a <= b) {
            long num = a * a + b * b;
            if(num == c) return true;
            else if (num < c) a++;
            else b--;
        }
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    string reverseVowels(string s) {
        string vowels = "aeiouAEIOU";
        int i = 0, j = s.size()-1;
        while (i < j) {
            if(vowels.find(s[i]) == -1) {
                i++;
                continue;
            }
            if(vowels.find(s[j]) == -1) {
                j--;
                continue;
            }
            swap(s[i], s[j]);
            i++, j--;
        }
        return s;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    bool validPalindrome(string s) {
        for (int i=0, j=s.size()-1; i<j; i++, j--) {
            if(s[i] != s[j]) {
                return isPalindrome(s, i+1, j) || isPalindrome(s, i, j-1);
            }
        }
        return true;
    }
    bool isPalindrome(string &s, int i, int j) {
        while (i < j && s[i] == s[j]) {
            i++, j--;
        }
        return i >= j;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m-1, j = n-1, k = m+n-1;
        while (j >= 0) {
            if (i < 0) {
                nums1[k--] = nums2[j--];
            } else if(nums1[i] < nums2[j]) {
                nums1[k--] = nums2[j--];
            } else {
                nums1[k--] = nums1[i--];
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast=head, *slow=head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        string res = "";
        for (string &t: dictionary) {
            int l1 = res.size(), l2 = t.size();
            if(l1 > l2 || (l1 == l2 && res.compare(t) < 0)) {   //当前字符串t的长度没有l1长 或者 长度相同但字典序更大
                continue;
            }
            if(isSubstr(s, t)) res = t; // 有更长的子串t
        }
        return res;
    }
    bool isSubstr(string &s, string &t) {
        int i=0, j=0;
        while (i < s.size()) {
            if(s[i] == t[j]) j++;
            i++;
        }
        return j == t.size();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        std::sort(g.begin(), g.end());
        std::sort(s.begin(), s.end());
        int i=0, j=0;
        while (i < g.size() && j < s.size()) {
            if(g[i] <= s[j]) i++;
            j++;
        }
        return i;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int mySqrt(int x) {
        if(x<=1) return x;
        int low = 1, high = x;
        while (low <= high) {   /// 退出循环时，high 总比 low 小1
            int mid = low + (high - low) / 2;
            int sqrt = x / mid;
            if (sqrt == mid) return mid;
            else if(sqrt < mid) high = mid - 1;
            else low = mid + 1;
        }
        return high;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int l = 0, r = letters.size()-1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            char c = letters[mid];
            if (c <= target) l = mid+1;
            else r = mid-1;
        }
        return l < letters.size() ? letters[l] : letters[0];
    }
};

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        auto pos = upper_bound(letters.begin(), letters.end(), target); /// 查找 >target 的第一个位置，返回对应的迭代器
        return pos == letters.end() ? letters[0] : *pos;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size();
        int l = 0, h = n - 1;
        while (l < h) {
            int mid = l + (h - l) / 2;
            if (mid % 2 == 1) { /// 保证查找的区间是奇数个元素， 即 l、mid、h都在偶数位
                mid --;
            }
            if (nums[mid] == nums[mid+1]) {
                l = mid + 2;
            } else {
                h = mid;
            }
        }
        return nums[l]; 
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, h = n;
        while (l < h) {
            int mid = l + (h - l) / 2;
            if (isBadVersion(mid)) {
                h = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0,  h = nums.size() - 1;
        while (l < h) {
            int m = l + (h - l) / 2;
            if (nums[m] <= nums[h]) h = m;
            else l = m+1;
        }
        return nums[l];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};
        int first = binarySearch(nums, target);         // 第一个 可能=target的值的索引
        int last = binarySearch(nums, target+1) - 1;    // 第二个可能=target的值的索引
        if(first == nums.size() || nums[first] != target) {
            // 找到的第一个元素nums[first]不是目标值 或者 已经是数组最后一个数了
            return {-1, -1};
        } else {
            return {first, last};
        }
    }
    int binarySearch(vector<int> &nums, int target) {
        int l = 0, h = nums.size(); // 注意h的值
        while (l < h) {
            int m = l + (h - l) / 2;
            if(nums[m] >= target) h = m;
            else l = m + 1;
        }
        return l;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

1
2
3
4
5
6
7
8

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int x: nums) res ^= x;
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0, sum;
        for (int i=0; i<32; i++) {
            sum = 0;
            for (int x: nums) {
                sum += ((x >> i) & 1); //(x>>i) & 1表示x的第i个二进制位
            }
            if(sum % 3) res = res | (1<<i);
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        /// n = nums.size(), 如果不缺少[0,n]的数 则res=0, 否则 res^i^nums[i]则是确实的nums[i]
        for (int i=0; i<nums.size(); i++) {
            res = res ^ i ^ nums[i];
        }
        return res ^ nums.size();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

/**
 * 两个不相等的元素在位级表示上必定会有一位存在不同。
将数组的所有元素异或得到的结果为不存在重复的两个元素异或的结果。
diff &= -diff 得到出 diff 最右侧不为 0 的位，也就是不存在重复的两个元素在位级表示上最右侧不同的那一位，利用这一位就可以将两个元素区分开来。
 */
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long diff = 0;
        for (auto x: nums) diff ^= x;
        diff &= -diff; // 得到最低位的1
        vector<int>res(2);
        for(int x: nums) {
            if((x & diff) == 0) res[0] ^= x;
            else res[1] ^= x;
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i=0; i<32; i++) {
            res = res << 1;
            res = res | (n & 1);
            n = n >> 1;
        }
        return res;
    }
};

1
2
3
4
5
6
7

class Solution {
public:
    bool isPowerOfTwo(int n) {
        /// n中只有一个1存在则 是2的n次方。 100 & 011 = 0;
        return n > 0 && (n & (n-1)) == 0;
    }
};

1
2
3
4
5
6
7

class Solution {
public:
    bool isPowerOfFour(int n) {
        //这种数在二进制表示中有且只有一个奇数位为 1，例如 16（10000）。
        return n > 0 && (n&(n-1)) == 0 && (n & 0b01010101010101010101010101010101) != 0;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

/**
/** Definition for a binary tree node.  
 struct TreeNode {  
     int val;  
	 TreeNode *left;  
	 TreeNode *right;  
	 TreeNode() : val(0), left(nullptr), right(nullptr) {}  
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}  
 };  
 */
 /**
  *  94. Binary Tree Inorder Traversal
  *  分析： 栈 或 Morris遍历；时间复杂度O(n), 空间复杂度分别为O(n), O(1)
  *  栈: 根节点左边的先全部加入栈 找到最左下的一个空节点， 然后打印栈顶节点，加入右子节点；继续迭代直到结束
  *  Morris 遍历 建立中序线索树
  */
// 00 递归
class Solution {
public:
    vector<int> result;
    void dfsInorderTravel(TreeNode* root) {
        if(root == nullptr) return;
        dfsInorderTravel(root->left);
        result.push_back(root->val);
        dfsInorderTravel(root->right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        dfsInorderTravel(root);
        return result;
    }
};

// 01 栈
class Solution {  
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result; // 存储结果序列
        stack<const TreeNode*> s;
        const TreeNode *p = root;
        while(!s.empty() || p != nullptr) {
            /// 栈非空 或 根节点非空
            if(p != nullptr) {
                s.push(p);
                p = p->left;
            } else {
                p = s.top();
                s.pop();
                result.push_back(p->val);
                p = p->right;
            }
        }
        return result;
    }
};

/// 02 Morros遍历 
//morris遍历的实质: 建立一种机制，对于没有左子树的节点只到达一次，对于有左子树的节点会到达两次
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        TreeNode *cur = root, *prev = nullptr;

        while (cur != nullptr) {
            /// 中序， 左根右 （建立中序线索树）
            /// 先检查是否存在左子树
            if (cur->left == nullptr) { // 不存在左子树
                result.push_back(cur->val);//保存要打印的父节点的值
                prev = cur; // 临时存储父节点，便于后面打印右子节点
                cur = cur->right;
            } else {    // 遍历左子树，查找root的前驱

                TreeNode *node = cur->left;
                while (node->right != nullptr && node->right != cur) { ///root的前驱为left tree的最右边的元素
                    node = node->right;
                }

                if (node->right == nullptr) { // 还没线索化，则建立线索
                    node->right = cur;
                    cur = cur->left;
                } else { // 已经线索化，则访问节点，并删除线索
                    result.push_back(cur->val);
                    node->right = nullptr;
                    prev = cur;
                    cur = cur->right;
                }
            }
        }
        return result;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

// 00 递归
class Solution {
public:
    vector<int> result;
    void dfsPreorderTravel(TreeNode* root) {
        if(root == nullptr) return;
        result.push_back(root->val);
        dfsPreorderTravel(root->left);
        dfsPreorderTravel(root->right);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        dfsPreorderTravel(root);
        return result;
    }
};

// 01 栈
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result; // 存储结果序列
        stack<const TreeNode*> s;
        if(root != nullptr) s.push(root);

        while(!s.empty()) {
            const TreeNode *p = s.top();
            s.pop();
            result.push_back(p->val);
            if(p->right != nullptr) s.push(p->right);
            if(p->left != nullptr) s.push(p->left);
        }
        return result;
    }
};

// 02 Morris遍历
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        TreeNode *cur = root, *prev = nullptr;
        while (cur != nullptr) {
            /// 前序遍历： 根左右（建立前序线索树）
            //先检查是否存在左子树
            if(cur->left == nullptr) {
                // 不存在左子树
                result.push_back(cur->val);
                prev = cur; // cur刚刚被访问过
                cur = cur->right;
            } else {
                // 存在左子树
                TreeNode *node = cur->left; // node为左子树的根节点
                while(node->right != nullptr && node->right != cur) {
                    node = node->right;
                }

                if(node->right == nullptr) { // 还没线索化，则建立线索
                    result.push_back(cur->val); //仅这里与中序不同
                    prev = cur; // cur刚刚被访问过
                    node->right = cur;
                    cur = cur->left;
                } else { // 已经线索化，则删除线索
                    node->right = nullptr;
                    cur = cur->right;
                }
            }
        }
        return result;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

//栈
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<const TreeNode*>s;
        // p: 正在访问的节点，刚刚访问过的节点
        const TreeNode *p = root, *q = nullptr;
        do {
            while(p != nullptr) {
                s.push(p);
                p = p->left;
            }
            q = nullptr;
            while(!s.empty()) {
                p = s.top();
                s.pop();
                if(p->right == q) {// 右孩子不存在或已被访问，则访问它
                    result.push_back(p->val);
                    q = p;
                } else {
                    // 存在右孩子，则不能访问当前节点
                    s.push(p);
                    p = p->right; // 先处理右子树
                    break;
                }
            }
        } while (!s.empty());
        return result;
    }
};

// TODO：Morris遍历 （较前序 中序 复杂）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

// 递归版
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        travel(root, 1, result);
        return result;
    }
    void travel(TreeNode* root, int level, vector<vector<int>> &result) {
        if(root == nullptr) return;
        if(level > result.size()) {
            result.push_back(vector<int>());
        }
        result[level-1].push_back(root->val);
        travel(root->left, level+1, result);
        travel(root->right, level+1, result);
    }
};

// 迭代版
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> current, next;
        if(root == nullptr) {
            return result;
        } else {
            current.push(root);
        }
        while(!current.empty()) {
            vector<int> level; // 存储一层里的元素
            while(!current.empty()) {
                TreeNode *node = current.front();
                current.pop();
                level.push_back(node->val);
                if(node->left != nullptr) next.push(node->left);
                if(node->right != nullptr) next.push(node->right);
            }
            result.push_back(level);
            swap(next, current); // current = next, next 为空队列
        }
        return result;
    }
};

1
2

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> current, next;
        if(root == nullptr) {
            return result;
        } else {
            current.push(root);
        }
        while(!current.empty()) {
            vector<int> level; // 存储一层里的元素
            while(!current.empty()) {
                TreeNode *node = current.front();
                current.pop();
                level.push_back(node->val);
                if(node->left != nullptr) next.push(node->left);
                if(node->right != nullptr) next.push(node->right);
            }
            result.push_back(level);
            swap(next, current); // current = next, next 为空队列
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

1
2

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> current, next;
        bool left_to_right = true;
        if(root == nullptr) {
            return result;
        } else {
            current.push(root);
        }
        while(!current.empty()) {
            vector<int> level; // 存储一层里的元素
            while(!current.empty()) {
                TreeNode *node = current.front();
                current.pop();
                level.push_back(node->val);
                if(node->left != nullptr) next.push(node->left);
                if(node->right != nullptr) next.push(node->right);
            }
            if(left_to_right == false) {
                reverse(level.begin(), level.end());
            }
            result.push_back(level);
            left_to_right = !left_to_right;
            swap(next, current); // current = next, next 为空队列
        }
        return result;
    }
};

// 内存优化 
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> current;
        bool left_to_right = true;
        if(root == nullptr) {
            return result;
        } else {
            current.push(root);
        }
        while(!current.empty()) {
            vector<int> level; // 存储一层里的元素
            int num = current.size();
            while(num--) { // num表示每一层的节点个数
                TreeNode *node = current.front();
                current.pop();
                level.push_back(node->val);
                if(node->left != nullptr) current.push(node->left);
                if(node->right != nullptr) current.push(node->right);
            }
            if(left_to_right == false) {
                reverse(level.begin(), level.end());
            }
            result.push_back(level);
            left_to_right = !left_to_right;
        }
        return result;
    }
};

1
2
3

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

1
2
3

Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

// 时间复杂度O(n), 空间复杂度O(1)
class Solution {
public:
    void recoverTree(TreeNode* root) {
        pair<TreeNode*, TreeNode*> swap_pair;
        TreeNode *prev = nullptr, *cur = root;

        while(cur != nullptr) {
            if(cur->left == nullptr) {
                detect(swap_pair, prev, cur);
                prev = cur;
                cur = cur->right;
            } else {
                // 存在左子树
                TreeNode* node = cur->left;
                while(node->right != nullptr && node->right != cur) { // 查找前驱
                    node = node->right;
                }
                if(node->right == nullptr) {
                    // 没有线索化，建立线索
                    node->right = cur;
                    cur = cur->left;
                } else {
                    // 已经建立了线索，则删除线索
                    node->right = nullptr;
                    detect(swap_pair, prev, cur);
                    prev = cur; // 访问过
                    cur = cur->right;
                }
            }
        }
        swap(swap_pair.first->val, swap_pair.second->val);
    }
    void detect(pair<TreeNode*, TreeNode*> &swap_pair, TreeNode* prev, TreeNode* cur) {
        if(prev != nullptr && prev->val > cur->val) {
            if (swap_pair.first == nullptr)
                swap_pair.first = prev;
            swap_pair.second = cur;
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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

// 迭代版
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        stack<TreeNode *>s;
        s.push(p);
        s.push(q);
        while(!s.empty()) {
            p = s.top(); s.pop();
            q = s.top(); s.pop();
            
            if(!p && !q) continue; // 都为空
            if(!p || !q) return false; // 有一个为空
            if(p->val != q->val) return false;
            
            s.push(p->left);
            s.push(q->left);
            s.push(p->right);
            s.push(q->right);
        }
        return true;
    }
};

1
2

Input: root = [1,2,2,3,4,4,3]
Output: true

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        stack<TreeNode *>s;
        TreeNode *p = root->left, *q = root->right;
        s.push(p), s.push(q);
        
        while(!s.empty()) {
            p = s.top(); s.pop();
            q = s.top(); s.pop();

            if(!p && !q) continue; // 都为空
            if(!p || !q) return false; // 有一个为空
            if(p->val != q->val) return false;

            s.push(p->left);
            s.push(q->right);
            s.push(p->right);
            s.push(q->left);
        }
        return true;
    }
};

1
2

Input: root = [3,9,20,null,null,15,7]
Output: true

1
2

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// 时间复杂度 O(logn) 
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return balanceHeight(root) >= 0;
    }
    int balanceHeight(TreeNode* root) {
        if(root == nullptr) return 0;
        int left = balanceHeight(root->left);
        int right = balanceHeight(root->right);

        if(left < 0 || right < 0 || abs(left-right) > 1) return -1;

        return max(left, right)+1;
    }
};

1
2

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

//时间复杂度O(n), 空间复杂度O(logn) 
// 递归版
class Solution {
public:
    void flatten(TreeNode* root) {
        if(!root) return ;

        flatten(root->left);
        flatten(root->right);

        if(root->left == nullptr) return;
        TreeNode *node = root->left;
        while(node->right != nullptr) // 找到根节点的前驱节点
            node = node->right;
        node->right = root->right;
        root->right = root->left;
        root->left = nullptr;
    }
};

// 迭代版
class Solution {
public:
    void flatten(TreeNode* root) {
        if(root == nullptr) return;

        stack<TreeNode *> s;
        s.push(root);
        while (!s.empty()) {
            auto p = s.top(); s.pop();

            if(p->right != nullptr) s.push(p->right);
            if(p->left != nullptr) s.push(p->left);
            p->left = nullptr;
            if(!s.empty()) p->right = s.top();
        }
    }
};

1
2
3
4
5
6

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

1
2
3

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

// 递归版； 时间复杂度O(n), 空间复杂度O(1)
/*
一旦在某层的节点之间建立了 \text{next}next 指针，那这层节点实际上形成了一个链表。因此，如果先去建立某一层的 \text{next}next 指针，再去遍历这一层，就无需再使用队列了。

基于该想法，提出降低空间复杂度的思路：如果第 ii 层节点之间已经建立 \text{next}next 指针，就可以通过 \text{next}next 指针访问该层的所有节点，同时对于每个第 ii 层的节点，我们又可以通过它的 \rm leftleft 和 \rm rightright 指针知道其第 i+1i+1 层的孩子节点是什么，所以遍历过程中就能够按顺序为第 i + 1i+1 层节点建立 \text{next}next 指针。

链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/solution/tian-chong-mei-ge-jie-dian-de-xia-yi-ge-you-ce-15/
*/
class Solution {
public:
    Node* connect(Node* root) {
        connected(root);
        return root;
    }
    void connected(Node* root) {
        if(root == nullptr) return ;

        Node dummy(-1);
        for (Node *cur = root, *prev = &dummy; cur != nullptr; cur = cur->next) {
            if(cur->left != nullptr) {
                prev->next = cur->left;
                prev = prev->next;
            }
            if(cur->right != nullptr) {
                prev->next = cur->right;
                prev = prev->next;
            }
        }
        connected(dummy.next);
    }
};

// 迭代版
class Solution {
public:
    Node* connect(Node* root) {
        Node* result = root;
        while(root) {
            Node* next = nullptr; // 下一层的第一个节点
            Node* prev = nullptr; // 同一层的前一个节点
            for( ; root != nullptr; root = root->next) {
                if(next == nullptr) {
                    // 获得下一层的第一个节点
                    next = root->left ? root->left : root->right;
                }
                if(root->left != nullptr) {
                    if(prev != nullptr)  // 避免Runtime error
                        prev->next = root->left;
                    prev = root->left;
                }
                if(root->right != nullptr) {
                    if(prev != nullptr) // 避免Runtime error
                        prev->next = root->right;
                    prev = root->right;
                }
            }
            root = next;
        }
        return result;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTreeByPreAndInorder(begin(preorder), end(preorder), begin(inorder), end(inorder));
    }

    template<typename InputIterator>
    TreeNode* buildTreeByPreAndInorder(InputIterator pre_first, InputIterator pre_last, InputIterator in_first, InputIterator in_last) {
        if (pre_first == pre_last) return nullptr;
        if (in_first == in_last) return nullptr;

        auto root = new TreeNode(*pre_first);
        auto in_root_pos = find(in_first, in_last, *pre_first); // 查找前序遍历元素在中序遍历中的位置对应的iterator
        auto left_size = distance(in_first, in_root_pos); // 左子树中的元素长度
        auto next_pre_last = next(pre_first, left_size+1); // 下一个pre_last对应位置的iterator

        root->left = buildTreeByPreAndInorder(next(pre_first), next_pre_last, in_first, in_root_pos);
        root->right = buildTreeByPreAndInorder(next_pre_last, pre_last, next(in_root_pos), in_last);

        return root;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return buildTreeByInorderAndPost(begin(inorder), end(inorder), begin(postorder), end(postorder));
    }

    template<typename InputIterator>
    TreeNode* buildTreeByInorderAndPost(InputIterator in_first, InputIterator in_last, InputIterator post_first, InputIterator post_last) {
        if (in_first == in_last) return nullptr;
        if (post_first == post_last) return nullptr;

        const auto val = *prev(post_last);
        auto root = new TreeNode(val);      // 以二叉树的根构建树
        
        auto in_root_pos = find(in_first, in_last, val);    // 查找后序遍历元素在中序遍历中的位置对应的iterator
        auto left_size = distance(in_first, in_root_pos); // 左子树中的元素列表长度
        auto post_left_last = next(post_first, left_size); 

        root->left = buildTreeByInorderAndPost(in_first, in_root_pos, post_first, post_left_last);
        root->right = buildTreeByInorderAndPost(next(in_root_pos), in_last, post_left_last, prev(post_last));

        return root;
    }
};

1
2

Input: n = 3
Output: 5

1
2

Input: n = 1
Output: 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// f(i) = \sum f(k-1) * (f(i-k), k \in [1, i], i \in [1,n] 
class Solution {
public:
    int numTrees(int n) {
        vector<int> f(n+1, 0);
        f[0] = 1, f[1] = 1;
        for(int i=2; i<=n; ++i) {
            for(int k=1; k<=i; ++k) {
                f[i] += f[k-1] * f[i-k];
            }
        }
        return f[n];
    }
};

class Solution {
public:
    int numTrees(int n) {
        long res = 1;
        for(int i=n+1; i<=2*n; ++i) {
            res = res * i / (i-n);
        }
       	return res / (n+1);
    }
};

1
2

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

1
2

Input: n = 1
Output: [[1]]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        return generate(1, n);
    }

private:
    vector<TreeNode*> generate(int start, int end) {
        vector<TreeNode*> sub_tree;
        if (start > end) {
            sub_tree.push_back(nullptr);
            return sub_tree;
        }
        for (int k = start; k <= end; ++k) {
            vector<TreeNode*> left_sub_tree = generate(start, k-1);
            vector<TreeNode*> right_sub_tree = generate(k+1, end);
            for(auto i: left_sub_tree) {
                for(auto j: right_sub_tree) {
                    TreeNode* node = new TreeNode(k);
                    node->left = i;
                    node->right = j;
                    sub_tree.push_back(node);
                }
            }
        }
        return sub_tree;
    }
};

1
2

Input: root = [2,1,3]
Output: true

1
2
3

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, LONG_MIN, LONG_MAX);
    }
    bool isValidBST(TreeNode* root, long lower, long upper) {
        if(root == nullptr) return true;

        return root->val > lower && root->val < upper
            && isValidBST(root->left, lower, root->val)
            && isValidBST(root->right, root->val, upper);
    }
};