Leetcode 数据结构入门

Leetcode 数据结构入门（C++）

每题第一个代码均为本人所写代码，并非最优解，部分解法参考题解。

第 1 天 数组

217. 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int,int> m;
        bool result=false;
        for(int i=0;i<nums.size();i++)
        {
            if(m.find(nums[i])==m.end())
                m[nums[i]]=1;
            else if(m[nums[i]])
            {
                result=true;
                break;
            }
        }
        return result;
    }
};
  • 时间复杂度：O(n)
  • 数组，哈希表

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum=nums[0],result=nums[0]; //以防只有负数
        for(int i=1;i<nums.size();i++)
        {
            if(sum<0)                   //sum若为负，加下一个数前先归零
                sum=0;
            sum+=nums[i];
            if(sum>result)
                result=sum;
        }
        return result;
    }
};
  • 时间复杂度：O(n)
  • 数组，动态规划

第 2 天 数组

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        unordered_map<int,int> hash; //哈希表
        for(int i=0;i<nums.size();i++)
        {
            if(hash.find(target-nums[i])!=hash.end()) //存在target-nums[i]
            {
                result.push_back(hash[target-nums[i]]);
                result.push_back(i);
                break;
            }
            hash[nums[i]]=i; //防止target=2*nums[i]
        }
        return result;
    }
};
  • 时间复杂度：O(n)
  • 数组，哈希表

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

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
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> result;
        int length=m+n;
        int r1=m,r2=n;
        for(int i=0;i<length;i++)
        {
            if(r1>0&&r2>0)
            {
                if(nums1[m-r1]<=nums2[n-r2])
                {
                    result.push_back(nums1[m-r1]);
                    nums1.pop_back();
                    r1--;
                }
                else
                {
                    result.push_back(nums2[n-r2]);
                    nums2.pop_back();
                    r2--;
                }
            }
            else if(r1>0)
            {
                result.push_back(nums1[m-r1]);
                nums1.pop_back();
                r1--;
            }
            else if(r2>0)
            {
                result.push_back(nums2[n-r2]);
                nums2.pop_back();
                r2--;
            }
        }
        nums1=result;
    }
};
  • 时间复杂度O(m+n)
  • 数组，排序

第 3 天 数组

350. 两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

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
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> hash1;
        for(int i=0;i<nums1.size();i++)
        {
            if(hash1.find(nums1[i])==hash1.end())
            {
                hash1[nums1[i]]=1;
            }
            else
            {
                hash1[nums1[i]]++;
            }
        }
        vector<int> result;
        for(int i=0;i<nums2.size();i++)
        {
            if(hash1[nums2[i]]>0)
            {
                hash1[nums2[i]]--;
                result.push_back(nums2[i]);
            }
        }
        return result;
    }
};
  • 时间复杂度：O(max(nums1.length, nums2.length)) 即O(n)
  • 数组，哈希表，排序

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result=0;
        int bgn=0x3f3f3f;
        for(int i=0;i<prices.size();i++) //动态规划：前i+1天的最低点 和 后n-i-1天的最高点
        {
            if(prices[i]<bgn)
            {
                bgn=prices[i];
            }
            if(prices[i]>bgn&&result<prices[i]-bgn)
            {
                result=prices[i]-bgn;
            }
        }
        return result;
    }
};
  • 时间复杂度：O(n)
  • 数组，动态规划

第 4 天 数组

566. 重塑矩阵

在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。

给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。

如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
        int m=mat.size();
        int n=mat[0].size();
        int num=m*n;
        if(r*c!=num)
            return mat;
        vector<vector<int>> result(r,vector<int>(c));   //注意初始化方式
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                result[i][j]=mat[(c*i+j)/n][(c*i+j)%n];
            }
        }
        return result;
    }
};
  • 时间复杂度：O(r*c)
  • 数组，矩阵，模拟

118. 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result(numRows);
        result[0]={1};
        for(int i=1;i<numRows;i++)
        {
            for(int j=0;j<i+1;j++)
            {
                int num=0;
                if(j-1>=0)
                    num+=result[i-1][j-1];
                if(j<=i-1)  
                    num+=result[i-1][j];
                result[i].push_back(num);
            }
        }
        return result;
    }
};
  • 时间复杂度：O(n^2)
  • 数组

第 5 天 数组

36. 有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

img

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
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for(int i=0;i<9;i++)
        {
            unordered_map<char,int> hash;
            for(int j=0;j<9;j++)
            {
                if(board[i][j]>='0'&&board[i][j]<='9')
                {
                    if(hash[board[i][j]]==0)
                    {
                        hash[board[i][j]]=1;
                    }
                    else
                    {
                        return false;
                    }
                }
                else
                    continue;
            }
        }
        for(int j=0;j<9;j++)
        {
            unordered_map<char,int> hash;
            for(int i=0;i<9;i++)
            {
                if(board[i][j]>='0'&&board[i][j]<='9')
                {
                    if(hash[board[i][j]]==0)
                    {
                        hash[board[i][j]]=1;
                    }
                    else
                    {
                        return false;
                    }
                }
                else
                    continue;
            }
        }
        for(int k=0;k<9;k++)
        {
            unordered_map<char,int> hash;
            for(int i=0;i<3;i++)
            {
                for(int j=0;j<3;j++)
                {
                    char num=board[k/3*3+i][k%3*3+j];
                    if(num>='0'&&num<='9')
                    {
                        if(hash[num]==0)
                        {
                            hash[num]=1;
                        }
                        else
                        {
                            return false;
                        }
                    }
                    else
                        continue;
                }
            }
        }
        return true;        
    }
};

  • 时间复杂度O(1)

  • 数组，矩阵，哈希表

73. 矩阵置零

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
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        //原地：原矩阵首行、首列记录0值，使得空间复杂度为O(1)
        int m=matrix.size();
        int n=matrix[0].size();
        bool first_row=0,first_col=0;
        //首行
        for(int j=0;j<n;j++)
        {
            if(matrix[0][j]==0)
            {
                first_row=1;
                break;
            }
        }
        //首列
        for(int i=0;i<m;i++)
        {
            if(matrix[i][0]==0)
            {
                first_col=1;
                break;
            }
        }
        //其他
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(matrix[i][j]==0)
                {
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
            }
        }
        //其他置0,别碰matrix[0][0]
        for(int j=1;j<n;j++)
        {
            if(matrix[0][j]==0)
            {
                for(int i=1;i<m;i++)
                {
                    matrix[i][j]=0;
                }
            }
        }
        for(int i=1;i<m;i++)
        {
            if(matrix[i][0]==0)
            {
                for(int j=1;j<n;j++)
                {
                    matrix[i][j]=0;
                }
            }
        }
        //首行置0
        if(first_row==1)
        {
            for(int j=0;j<n;j++)
            {
                matrix[0][j]=0;
            }
        }
        if(first_col==1)
        {
            for(int i=0;i<m;i++)
            {
                matrix[i][0]=0;
            }            
        }
    }
};
  • 时间复杂度O(m*n)
  • 空间复杂度O(1)
  • 数组，矩阵

第 6 天 字符串

387. 字符串中的第一个唯一字符

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char,int> hash;
        for(int i=0;i<s.length();i++)
        {
            hash[s[i]]++;
        }
        for(int i=0;i<s.length();i++)
        {
            if(hash[s[i]]==1)
                return i;
        }
        return -1;
    }
};

  • 时间复杂度：O(n)

  • 字符串，哈希表

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char,int> hash;
        for(int i=0;i<magazine.length();i++)
        {
            hash[magazine[i]]++;
        }
        for(int i=0;i<ransomNote.length();i++)
        {
            hash[ransomNote[i]]--;
            if(hash[ransomNote[i]]<0)
                return false;
        }
        return true;
    }
};
  • 时间复杂度：O(max(ransomNotr,magazine)) 即O(n)
  • 字符串，哈希表，计数

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

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:
    bool isAnagram(string s, string t) {
        unordered_map<char,int> hash;
        for(int i=0;i<s.length();i++)
        {
            hash[s[i]]++;
        }
        for(int i=0;i<t.length();i++)
        {
            hash[t[i]]--;
            if(hash[t[i]]<0)    //t中某字符个数多于s
                return false;
        }
        for(int i=0;i<s.length();i++)
        {
            if(hash[s[i]]>0)    //s中某字符个数多于t
                return false;
        }
        return true;
    }
};
  • 时间复杂度：O(max(s.length(),t.length())) 即O(n)
  • 字符串，哈希表

第 7 天 链表

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *now=head;
        while(now!=NULL&&now->next!=NULL)
        {
            if(now->val==100001)
            {
                return true;
            }
            now->val=100001;
            now=now->next;
        }
        return false;
    }
};
  • 时间复杂度：O(n)
  • 链表

2. 快慢指针（推荐）

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==NULL)
            return list2;
        if(list2==NULL)
            return list1;
        if(list1->val<list2->val)  //留下小的(返回头节点即可)
        {
            list1->next=mergeTwoLists(list1->next,list2);
            return list1;
        }
        else
        {
            list2->next=mergeTwoLists(list1,list2->next);
            return list2;
        }
    }
};
  • 时间复杂度：O(n+m)，其中n、m分别为两链表长度
  • 递归，链表

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *H= new ListNode(); //头节点（非空则可引用）
        H->next=head;
        ListNode *p=H;
        while(p!=NULL&&p->next!=NULL) //遍历删除满足条件的节点
        {
            if(p->next->val==val)
            {
                p->next=p->next->next;
            }
            else
                p=p->next;
        }
        return H->next;
    }
};
  • 时间复杂度：O(n)，n为链表长度
  • 链表

第 8 天 链表

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* res=NULL;				//注意尾节点必须指向NULL
        ListNode* cur=head;
        while(cur!=NULL)
        {
            ListNode* temp=cur;
            cur=cur->next;
            temp->next=res;
            res=temp;
        }
        return res;
    }
};
  • 时间复杂度：O(n)，n为链表长度
  • 链表

83. 删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* cur=head;
        while(cur!=NULL)
        {
            if(cur->next!=NULL&&cur->next->val==cur->val)
            {
                cur->next=cur->next->next;
            }
            else 
            {
                cur=cur->next;
            }
        }
        return head;
    }
};
  • 时间复杂度：O(n)，n为链表长度
  • 链表

第 9 天 栈/队列

20. 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

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
class Solution {
public:
    bool isValid(string s) {
        stack<char> left;
        int len=s.length();
        for(int i=0;i<len;i++)
        {
            if(s[i]=='('||s[i]=='{'||s[i]=='[')
            {
                left.push(s[i]);
            }
            else if(left.empty())
            {
                return false;
            }
            else
            {
                char ch=left.top();
                left.pop();
                if(s[i]==')'&&ch!='(')
                    return false;
                else if(s[i]=='}'&&ch!='{')
                    return false;
                else if(s[i]==']'&&ch!='[')
                    return false;
            }
        }
        if(left.size())
            return false;
        return true;
    }
};

  • 时间复杂度：O(n)，n为字符串长度

  • 栈，字符串

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

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 MyQueue {
public:
    stack<int> a;
    stack<int> b;
    MyQueue() {

    }
    
    void push(int x) {
        a.push(x);
    }
    
    int pop() {
        //构建b：按队列顺序出栈
        while(!a.empty())
        {
            b.push(a.top());
            a.pop();
        }
        //记录返回值，且去掉队首元素
        int ret=b.top();
        b.pop();
        //恢复a
        while(!b.empty())
        {
            a.push(b.top());
            b.pop();
        }
        return ret;
    }
    
    int peek() {
        //构建b：按队列顺序出栈
        while(!a.empty())
        {
            b.push(a.top());
            a.pop();
        }
        //记录返回值
        int ret=b.top();
        //恢复a
        while(!b.empty())
        {
            a.push(b.top());
            b.pop();
        }
        return ret;
    }
    
    bool empty() {
        return a.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */
  • 栈，设计，队列

第 10 天 树

144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

迭代法

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:
    //根 左 右
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> data; //待处理数据
        TreeNode* p=root;
        while(p!=NULL)
        {
            if(p->right!=NULL)
                data.push(p->right);
            if(p->left!=NULL)
                data.push(p->left);
            ret.push_back(p->val);
            if(data.empty())
                break;
            p=data.top();
            data.pop();
        }
        return ret;
    }
};
  • 时间复杂度：O(n)，n为节点个数
  • 栈，树，二叉树

模板：

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
/**
 * 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) {}
 * };
 */
class Solution {
public:
    //根 左 右
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        if(!root) 
            return result;
        stack<TreeNode*> stk; 
        stk.push(root);
        while(!stk.empty())
        {
            TreeNode* node = stk.top();
            stk.pop();
            if(node)
            {
                if(node -> right){
                    stk.push(node -> right);
                }
                if(node -> left){
                    stk.push(node -> left);
                } 
                stk.push(node);
                stk.push(nullptr);
            }
            else
            {
                result.push_back(stk.top()->val);
                stk.pop();
            }
        }
        return result;
    }
};

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

迭代

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:
    //左 根 右
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> data; //待处理数据
        TreeNode* p=root;
        while(p!=NULL||!data.empty())
        {
            while(p!=NULL) //左链入栈
            {
                data.push(p);
                p=p->left;
            }
            p=data.top();
            data.pop();
            ret.push_back(p->val);
            p=p->right;
        }
        return ret;
    }
};
  • 时间复杂度：O(n)，n为节点个数
  • 栈，树，二叉树

模板：

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> inorderTraversal(TreeNode* root) {
        vector<int> result;
        if(!root) 
            return result;
        stack<TreeNode*> stk; 
        stk.push(root);
        while(!stk.empty())
        {
            TreeNode* node = stk.top();
            stk.pop();
            if(node)
            {
                if(node -> right){
                    stk.push(node -> right);
                }
                stk.push(node);
                stk.push(nullptr); //分隔父节点和子节点，作为输出（入结果栈）标识                
                if(node -> left){
                    stk.push(node -> left);
                } 
            }
            else
            {
                result.push_back(stk.top()->val);
                stk.pop();
            }
        }
        return result;
    }
};

145. 二叉树的后序遍历

给你一棵二叉树的根节点 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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) {}
 * };
 */
class Solution {
public:
    //左 右 根
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if(!root) 
            return result;
        stack<TreeNode*> stk; 
        stk.push(root);
        while(!stk.empty())
        {
            TreeNode* node = stk.top();
            stk.pop();
            if(node)
            {
                stk.push(node);
                stk.push(nullptr); //分隔父节点和子节点，作为输出（入结果栈）标识
                if(node -> right){
                    stk.push(node -> right);
                }
                if(node -> left){
                    stk.push(node -> left);
                } 
            }
            else
            {
                result.push_back(stk.top()->val);
                stk.pop();
            }
        }
        return result;
    }
};

第 11 天 树

102. 二叉树的层序遍历

给你二叉树的根节点 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 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) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> now; //当前层，先进先出
        now.push(root);
        TreeNode* p;
        vector<vector<int>> result;
        while(!now.empty())
        {
            queue<TreeNode*> next; //下一层
            vector<int> vec;
            while(!now.empty())
            {
                p=now.front();
                now.pop();
                if(p)
                {
                    vec.push_back(p->val);
                    if(p->left)
                        next.push(p->left);
                    if(p->right)
                        next.push(p->right);
                }
            }
            if(!vec.empty())
                result.push_back(vec);
            now=next;   
        }
        return result;
    }
};
  • 时间复杂度：O(n)，n为节点个数
  • 树，广度优先搜索，二叉树

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 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) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
            return root==NULL? 0 : max(maxDepth(root->left),maxDepth(root->right))+1; 
    }
};
  • 时间复杂度：O(n)，n为节点个数
  • 树，深度优先搜索，二叉树

101. 对称二叉树

给你一个二叉树的根节点 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
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
/**
 * 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) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> left;
        queue<TreeNode*> right;
        if(root->left)
            left.push(root->left);
        if(root->right)
            right.push(root->right);
        TreeNode* p=root;
        TreeNode *l,*r;
        while(!left.empty()||!right.empty())
        {
            if(left.size()!=right.size())
                return false;
            l=left.front();
            left.pop();
            r=right.front();
            right.pop();
            if(l->val!=r->val)
                return false;
            if(l->left)
            {
                left.push(l->left);
                if(r->right==NULL)
                    return false;
            }
            if(l->right)
            {
                left.push(l->right);
                if(r->left==NULL)
                    return false;
            }
            if(r->right)
            {
                right.push(r->right);
                if(l->left==NULL)
                    return false;
            }
            if(r->left)
            {
                right.push(r->left);
                if(l->right==NULL)
                    return false;
            }
        }
        return true;
    }
};
  • 时间复杂度：O(n)，n为节点个数
  • 树，广度优先搜索，二叉树

第 12 天 树

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root)
            return root;
        swap(root->left,root->right);
        root->left=invertTree(root->left);
        root->right=invertTree(root->right);
        return root;
    }
};
  • 时间复杂度：O(n)，n为节点个数
  • 树，二叉树，深度优先搜索

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点

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
 * 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) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root) //树是空的
        {
            return false;
        }
        else if(!root->left&&!root->right) //叶节点
        {
            if(targetSum!=root->val)
                return false;
            else
                return true;
        }
        else  //其他节点
        {
            return hasPathSum(root->left,targetSum-root->val)||hasPathSum(root->right,targetSum-root->val);
        }     
    }
};
  • 树，深度优先搜索，二叉树

第 13 天 树

700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root==NULL)
            return NULL;
        else if(root->val==val)
            return root;
        else if(root->val<val)
            return searchBST(root->right,val);
        else
            return searchBST(root->left,val);
    }
};
  • 时间复杂度：O(logN)
  • 树，二叉树，二叉搜索树

701. 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

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
/**
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode *p=root;
        TreeNode *node=new TreeNode(val); 
        if(root==NULL)
            return node;
        while(p)
        {
            if(val<p->val)
            {
                if(p->left)
                    p=p->left;
                else
                {
                    p->left=node;
                    break;
                }
            }
            else
            {
                if(p->right)
                    p=p->right;
                else
                {
                    p->right=node;
                    break;
                }
                    
            }
        }
        return root;
    }
};
  • 时间复杂度：O(logN)
  • 树，二叉树，二叉搜索树
  • 遍历法

第 14 天 树

98. 验证二叉搜索树

给你一个二叉树的根节点 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
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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) {}
 * };
 */
class Solution {
    //思路：BST树的中序遍历是升序的
public:
    bool isValidBST(TreeNode* root) {
        long long int lastVal=LONG_MIN; //前驱节点的值(注意卡边界值的情况)
        stack<TreeNode*> data; //待处理数据
        TreeNode* p=root;
        while(p!=NULL||!data.empty())
        {
            while(p!=NULL) //左链入栈
            {
                data.push(p);
                p=p->left;
            }
            p=data.top();
            data.pop();
            if(p->val<=lastVal)
                return false;
            else
                lastVal=p->val;
            p=p->right;
        }
        return true;
    }
};
  • 时间复杂度$O(n)$,n为结点数
  • 树，二叉树，二叉搜索树，深度优先搜索

653. 两数之和 IV - 输入 BST

给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

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
/**
 * 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) {}
 * };
 */
class Solution {
public:
    //中序遍历：升序
    bool findTarget(TreeNode* root, int k) {
        vector<int> ret;
        stack<TreeNode*> data; //待处理数据
        TreeNode* p=root;
        while(p!=NULL||!data.empty())
        {
            while(p!=NULL) //左链入栈
            {
                data.push(p);
                p=p->left;
            }
            p=data.top();
            data.pop();
            ret.push_back(p->val);
            p=p->right;
        }
        // 双指针指向首、尾
        int l=0,r=ret.size()-1;
        while(l<r)
        {
            if(ret[l]+ret[r]==k)
                return true;
            if(ret[l]+ret[r]<k)
                l++;
            else
                r--;    
        }
        return false;
    }
};
  • 时间复杂度$O(n)$,n为结点数
  • 树，二叉树，二叉搜索树，深度优先搜索，双指针

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

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
/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //等于根
        if(p->val==root->val||q->val==root->val)
            return root;
        //在根两边
        else if((p->val<root->val)^(q->val<root->val))
            return root;
        //在根左边
        else if(p->val<root->val)
            return lowestCommonAncestor(root->left,p,q);
        //在根右边
        else
            return lowestCommonAncestor(root->right,p,q);
    }
};
  • 树，二叉树，二叉搜索树，深度优先搜索