链表相关操作

1、删除排序链表重复结点

//迭代更好理解
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        auto cur = head;
        for(auto p = head->next; p; p = p->next)
            if(p->val != cur->val)
                cur = cur->next = p;

        cur->next = NULL;
        return head;
    }
};
//递归很妙，但后面再写代码可能就写不出来了
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
         if(!head || !head->next){
            return head;
        }
        head->next = deleteDuplicates(head->next);
        if(head->val == head->next->val) head = head->next;
        return head;
    }
};

2、删除链表所有重复结点||

//凡是涉及到删除头结点就设一个虚拟头结点，简化代码
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto p = dummy;
        while(p->next){
            auto q = p->next;
            while(q && q->val == p->next->val) q = q->next;
            //判断p和q之间有几个点
            if(q == p->next->next) p = p->next;
            else p->next = q;
        }
        return dummy->next;
    }
};

3、反转链表

//迭代
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = NULL, *cur = head, *next = NULL;
        while(cur){
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};
//递归
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;

        ListNode* node = reverseList(head->next);
        head->next->next = head;
        head->next = NULL; 
        return node;
    }
};

4、合并两个排序的链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1), tail = dummy;
        while(l1 && l2){
            if(l1->val < l2->val){
                tail = tail->next = l1;
                l1 = l1->next;
            } else {
                tail = tail->next = l2;
                l2 = l2->next;
            }
        }
        if(l1) tail->next = l1;
        if(l2) tail->next = l2;

        return dummy->next;
    }
};

5、重排链表

class Solution {
public:
    void rearrangedList(ListNode* head) {
        if(!head->next) return ;
        int n = 0;
        for(auto p = head; p; p = p->next)  n++;


        int left = (n + 1) / 2;
        auto a = head;
        for(int i = 0; i < left - 1; i ++)  a = a->next;
        auto b = a->next, c = b->next;

        a->next = b->next = NULL;
        while(c){
            auto p = c->next;
            c->next = b;
            b = c, c = p;
        }

        //合并两个链表
        for(auto p = head, q = b; q ;){
            auto t = q->next;
            q->next = p->next;
            p->next = q;
            p = p->next->next;
            q = t;
        }
    }
};

6、链表排序

class Solution {
public:

    deque<int> que;
    ListNode* sortList(ListNode* head) {
        auto p = head;
        while(p){ //取出链表元素
            que.push_back(p->val);
            p = p->next;
        }

        sort(que.begin(), que.end());

        auto q = head;
        while(q){ //结果放回链表
            q->val = que.front(), que.pop_front();
            q = q->next;
        }
        return head;
    }
};

7、回文链表

请判断是否为回文链表

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> res;
        while(head){
            res.push_back(head->val);
            head = head->next;
        }
        vector<int> t = res;
        reverse(t.begin(), t.end());
        return t == res;
    }
};

8、环形链表

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

9、相交链表

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto p = headA, q = headB;
        while(p != q){
            p = p ? p->next : headB;
            q = q ? q->next :headA;
        }
        return p;
    }
};

10、单链表插入排序

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode *dummy = new ListNode(-1), *pre;
        dummy->next = head;

        while(head && head->next){
            if(head->val <= head->next->val){
                head = head->next;
                continue;
            }
            pre = dummy;

            while(pre->next->val < head->next->val) pre = pre->next;

            auto cur = head->next;
            head->next = cur->next;
            cur->next = pre->next;
            pre->next = cur;
        }
        return dummy->next;
    }
};

11、分隔链表（有点类似快排）

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        auto dummy1 = new ListNode(-1), dummy2 = new ListNode(-1);
        auto tail1 = dummy1, tail2 = dummy2;
        for(auto p = head; p; p = p->next){
            if(p->val < x) tail1 = tail1->next = p;
            else tail2 = tail2->next = p;
        }
        tail1->next = dummy2->next;
        tail2->next = NULL;
        return dummy1->next;
    }
};

12、链表中环的第一个结点

//哈希表
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> hash;
        for(auto p = head; p; p = p->next){
            if(hash.count(p))   
                return p;
            else 
                hash.insert(p);
        }
        return NULL;
    }
};

//快慢指针
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head,*fast = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                fast = head;
                while(slow != fast){
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return NULL;
    }
};

二叉树

1、二叉树的深度

 class Solution {
public:
    int treeDepth(TreeNode* root) {
        if(!root) return 0;
        int left = treeDepth(root->left);
        int right = treeDepth(root->right);
        return max(left, right) + 1;
    }
};

2、是否是平衡二叉树

class Solution {
public:

    bool ans = true;

    bool isBalanced(TreeNode* root) {
        dfs(root);
        return ans;
    }

    int dfs(TreeNode* root){
        if(!root)   return 0;
        int left = dfs(root->left), right = dfs(root->right);
        if(abs(right - left) > 1)   ans = false;
        return max(left, right) + 1;
    }
};

3、是否是完全二叉树

//此题应该不能用递归，有特例无法满足
bool is_complete(TreeNode* root)
{
    if(!root) return true;

    queue<int> q;
    TreeNode* cur;
    q.push(root);
    //进行层次遍历
    while((cur = q.pop()) != NULL)
    {
        q.push(root->left);
        q.push(root->right);
    }
    //判断是否未被访问的结点
    while(!q.is_empty())
    {
        cur = q.pop();
        if(!cur) return false;
    }
    return ture;;
}
//另外还有数组的思路也十分巧妙：
    填数据，从根节点开始遍历，如果是完全二叉树，刚好可以填进1-n (根节点位置是1)
    否则最后一个节点的位置一定大于n
void dfs(int root, int k)
{
    if(max_k < k)
    {
        lastu = root;
        max_k = k;
    }
    if(l[root] != -1) dfs(l[root], 2 * k);     //左孩子
    if(r[root] != -1) dfs(r[root], 2 * k + 1); //右孩子
}

4、判断是否是二叉搜索树

//非递归：中序遍历存入一个数组当中，如果是从小到大排列就是二叉搜索树
class Solution {
public:

    vector<int> vec;

    void dfs(TreeNode* root){
        if(!root) return ;
        dfs(root->left);
        vec.push_back(root->val);
        dfs(root->right);
    }

    bool isValidBST(TreeNode* root) {
        dfs(root);
        for(int i = 1; i < vec.size(); i++){
            if(vec[i] <= vec[i - 1]) return false;
        }
        return true;
    }
};
//递归
class Solution {
public:
    long long maxVal = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        bool left = isValidBST(root->left);
        //中序遍历,验证遍历的元素是不是从小到大
        if(maxVal < root->val)  
            maxVal = root->val;
        else 
            return false;
        bool  right = isValidBST(root->right);
        return left && right;
    }
};

5、将有序数组转换为二叉搜索树

//把数组元素的中间元素作为根结点，递归的建立左子树、右子树即为所求二叉搜索树(有证明)
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(nums, 0, nums.size() - 1);
    }

    TreeNode* build(vector<int>& nums, int l, int r){
        if(l > r)  return NULL;
        int mid = l + r >> 1;
        auto root = new TreeNode(nums[mid]);
        root->left = build(nums, l, mid - 1);
        root->right = build(nums, mid + 1, r);
        return root;
    }
};

6、有序链表转换为平衡的二叉搜索树

//开一个数组存链表元素，这就转化为上一题
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        vector<int> nums;
        for(auto p = head; p; p = p->next)  nums.push_back(p->val);
        return build(nums, 0, nums.size() - 1);
    }

    TreeNode* build(vector<int>& nums, int l, int r){
        if(l > r) return NULL;
        int mid = (l + r) >> 1;
        auto root = new TreeNode(nums[mid]);
        root->left = build(nums, l, mid - 1);
        root->right = build(nums, mid + 1, r);
        return root;
    }
};

//直接遍历链表
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(!head) return NULL;
        int n = 0;
        for(auto p = head; p; p = p->next) n++;
        if(n == 1) return new TreeNode(head->val);
        auto cur = head;
        //遍历到中点的前一个点
        for(int i = 0; i < n / 2 - 1; i++) cur = cur->next;
        auto root = new TreeNode(cur->next->val);
        root->right = sortedListToBST(cur->next->next);
        cur->next = NULL;
        root->left = sortedListToBST(head);
        return root;
    }
};

7、二叉树叶节点的个数

int node_num(TreeNode* root, int &cnt)
{
    if(!root) return 0;
    if(!root->left && !root->right) cnt++;
    else if(root->left)
        node_num(root->left, cnt);
    else
        node_num(root->left, cnt);
    return cnt;
}

8、交换二叉树的左右儿子，镜像二叉树

TreeNode* inverTree(TreeNode* root)
{
    if(root)
    {
        swap(root->left, root->right);
        inverTree(root->left);
        inverTree(root->right);
    }
    return root;
} 

9、对称二叉树

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return dfs(root->left, root->right);
    }

    bool dfs(TreeNode* p, TreeNode* q){
        //两个空结点左右对称
        if(!p && !q) return true;
        //其中一个是空或者节点值不一样
        if(!p || !q || p->val != q->val) return false;
        return dfs(p->left, q->right) && dfs(p->right, q->left);
    }
};

10、二叉树的层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector< vector<int> > res;
        queue<TreeNode*> q;
        if(root) q.push(root);

        while(q.size()){
            vector<int> level;
            int len = q.size();

            while(len --){
                auto t = q.front(); q.pop();
                level.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            res.push_back(level);
        }
        return res;
    }
};

11、二叉树自下往上的层序遍历

//只需把正常层序遍历的答案数组反转以下就行了
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector< vector<int> > res;
        queue<TreeNode*> q;
        if(root) q.push(root);
        while(q.size()){
            vector<int> level;
            int len = q.size();
            while(len --){
                auto t = q.front(); q.pop();
                level.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            res.push_back(level);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

12、从上往下打印二叉树

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<int> res;
        if(root) q.push(root);

        while(q.size()){
            vector<int> level;
            int len = q.size();
            while(len --){
                auto t = q.front(); q.pop();
                res.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
        }
        return res;
    }
};

13、合并二叉树

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1) return root2;
        if(!root2) return root1;

        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};

14、二叉树剪枝

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(!root) return NULL;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        if(!root->left && !root->right && root->val == 0)   return NULL;
        return root;
    }
};

15、展平二叉搜索树

class Solution {
public:
    TreeNode *dummy = new TreeNode(-1), *node = dummy;
    TreeNode* increasingBST(TreeNode* root) {
        dfs(root);
        return dummy->right;       
    }

    void dfs(TreeNode* root){
        if(!root) return ;
        dfs(root->left);
        //创建右儿子
        node->right = new TreeNode(root->val);
        node = node->right;
        dfs(root->right);
    }
};

16、二叉树最底层最左边的值

//思路：层序遍历
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode *> q;
        int res;
        q.push(root);
        while(!q.empty()){
            int len = q.size();
            for(int i = 0; i < len; i++)
            {
                if(i == 0)  res = q.front()->val;
                auto t = q.front(); q.pop(); //取出队头元素
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
        }
        return res;
    }
};

17、手写哈夫曼树

#include <iostream>
#include <queue>

using namespace std;

int main(){

    priority_queue<int, vector<int>, greater<int> > heap; //建一个小根堆

    int n; cin >> n;
    for(int i = 0; i < n; i++){
        int w;
        cin >> w;
        heap.push(w);
    }

    int res = 0;
    while(heap.size() > 1)
    {
        int x = heap.top(); heap.pop();
        int y = heap.top(); heap.pop();
        res += x + y;
        heap.push(x + y);
    }

    cout << res << endl;
    return 0;
}

二叉树的遍历递归代码

//中序遍历
class Solution {
public:

    vector<int> res;
    vector<int> inorderTraversal(TreeNode* root) {    
        dfs(root);
        return res;
    }

    void dfs(TreeNode* root){
        if(!root) return ;
        dfs(root->left);   //左
        res.push_back(root->val);  //根
        dfs(root->right);   //右
    }
};

//前序遍历
void pre_dfs(TreeNode* root){
    if(!root) return ;
    res.push_back(root->val);  //根
    dfs(root->left);   //左
    dfs(root->right);   //右
}
//后序遍历
void pre_dfs(TreeNode* root){
    if(!root) return ;
    dfs(root->left);   //左
    dfs(root->right);   //右
    res.push_back(root->val);  //根
}

二叉树遍历迭代

//前序遍历（非递归写法）
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while(root || stk.size()){
            while(root){
                res.push_back(root->val);
                stk.push(root);
                root = root->left;
            }
            root = stk.top()->right;
            stk.pop();
        }
        return res;
    }
};

//中序遍历
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while(root || stk.size()){
            while(root){
                stk.push(root);
                root = root->left;
            }
            if(stk.size()){
                root = stk.top(); stk.pop();
                res.push_back(root->val);
                root = root->right;
            }
        }
        return res;
    }
};

//后序遍历：手动更改前序遍历访问操作为根右左，再翻转一下答案即得：左右根，输出的结果就是后序遍历
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;  //存放结果数组
        stack<TreeNode*> stk;
        while(root || stk.size()){
            while(root){
                res.push_back(root->val);
                stk.push(root);
                root = root->right;
            }
            root = stk.top()->left;
            stk.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

18、根据先序遍历和中序遍历还原二叉树

class Solution {
public:

    unordered_map<int, int> pos;
    vector<int> preorder, inorder;

    TreeNode* build(int a, int b, int x, int y){
        if(a > b)   return NULL;
        auto root = new TreeNode(preorder[a]);
        int k = pos[root->val];
        root->left = build(a + 1, a + 1 + k - 1 - x, x, k - 1);
        root->right = build(a + 1 + k - 1 - x + 1, b, k + 1, y);
        return root;
    }

    TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder){
        preorder = _preorder, inorder = _inorder;
        int n = inorder.size();
        for(int i = 0; i < n; i ++) pos[inorder[i]] = i;
        return build(0, n - 1, 0, n - 1);
    }
};

19、表达式树转中缀表达式（2017年408）

class Solution {
public:
    string dfs(TreeNode* root){
        if(!root)   return "";
        if(!root->left && !root->right) return root->val;
        return '(' + dfs(root->left) + root->val + dfs(root->right) + ')';
    }

    string expressionTree(TreeNode* root) {
        return dfs(root->left) + root->val + dfs(root->right);
    }
};

[20、]二叉树的带权路径长度](https://www.acwing.com/problem/content/3769/)

class Solution {
public:

    int dfs(TreeNode* root, int depth){
        if(!root)   return 0;
        if(!root->left && !root->right) return root->val * depth;
        return dfs(root->left, depth + 1) + dfs(root->right, depth + 1);
    }

    int pathSum(TreeNode* root) {
        return dfs(root, 0);
    }
};

ps:此贴仅为笔者汇总可能会考的小题，方便平时练习巩固，加强记忆。代码均为笔者认为最精炼易懂的，写出来供大家参考。