LeetCode + 《剑指Offer II》刷题笔记。
树
二叉树的DFS
Preorder Traversal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode* cur=root;
while(cur || !s.empty()){
while(cur){
res.push_back(cur->val);
s.push(cur);
cur=cur->left;
}
cur=s.top();
s.pop();
cur=cur->right;
}
return res;
}
};
|
Inorder Traversal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode* cur=root;
while(cur || !s.empty()){
while(cur){
s.push(cur);
cur=cur->left;
}
cur=s.top();
s.pop();
res.push_back(cur->val);
cur=cur->right;
}
return res;
}
};
|
Postorder Traversal
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
|
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode* cur=root;
TreeNode* prev;
while(cur || !s.empty()){
while(cur){
s.push(cur);
cur=cur->left;
}
cur=s.top();
if(cur->right && cur->right!=prev){
cur=cur->right;
}else{
s.pop();
res.push_back(cur->val);
prev=cur;
cur=nullptr;
}
}
return res;
}
};
|
OR
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> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode* cur=root;
//postorder:left right root
//reverse:root right left -- similar with inorder
while(cur || !s.empty()){
while(cur){
s.push(cur);
res.push_back(cur->val);
cur=cur->right;
}
cur=s.top();
s.pop();
cur=cur->left;
}
reverse(res.begin(),res.end());
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
TreeNode* pruneTree(TreeNode* root) {
if(!root) return root;
root->left=pruneTree(root->left);
root->right=pruneTree(root->right);
if(!root->left && !root->right && !root->val){
root=nullptr;
}
return root;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
|
class Solution {
public TreeNode pruneTree(TreeNode root) {
if(root==null) return root;
root.left=pruneTree(root.left);
root.right=pruneTree(root.right);
if(root.val==0 && root.left==null && root.right==null){
return null;
}
return root;
}
}
|
297 Serialize and Deserialize Binary Tree
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
|
class Codec {
public:
void rserialize(TreeNode* root,string& str){
if(!root) str+="None,";
else{
str+=to_string(root->val)+",";
rserialize(root->left,str);
rserialize(root->right,str);
}
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string ret;
rserialize(root,ret);
return ret;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
list<string> dataArray;
string str;
for(auto& ch:data){
if(ch==','){
dataArray.push_back(str);
str.clear();
}else{
str.push_back(ch);
}
}
if(!str.empty()){
dataArray.push_back(str);
str.clear();
}
return rdeserialize(dataArray);
}
TreeNode* rdeserialize(list<string>& dataArray){
if(dataArray.front()=="None"){
dataArray.erase(dataArray.begin());
return nullptr;
}
TreeNode* root=new TreeNode(stoi(dataArray.front()));
dataArray.erase(dataArray.begin());
root->left=rdeserialize(dataArray);
root->right=rdeserialize(dataArray);
return root;
}
};
|
注意：
1、这里使用的是list<string> dataArray;
2、使用list和特殊字符",“将字符串分割为字符数组的技巧。
自己使用 find(c,startpos) 和 substrate(pos,n) 实现字符串分割的解法提交会有Time Limit Exceeded.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
vector<string> res;
int start = 0;
while (data.find(',', start) != string::npos)
{
// find(c,startpos)
int index = data.find(',', start);
// substr(pos,n)
res.push_back(data.substr(start, index - start));
start = index + 1;
}
return rdeserialize(res);
}
|
OR
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
vector<string> res;
string str;
int start=0;
for(int i=0;i<data.length();i++){
if(data[i]==','){
str=data.substr(start,i-start);
res.push_back(str);
start=i+1;
}
}
return rdeserialize(res);
}
|
这两种方法都会有Time Limit Exceeded.
129 Sum Root to Leaf Numbers
深度优先搜索更加适合解决与路径相关的面试题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
int sumNumbers(TreeNode* root) {
return preorder(root,0);
}
int preorder(TreeNode* root,int sum){
if(root){
sum=sum*10+root->val;
if(!root->left && !root->right) return sum;
return preorder(root->left,sum)+preorder(root->right,sum);
}
return 0;
}
};
|
- 时间复杂度：O(n)
- 空间复杂度：O(H)，其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销。最坏情况下，树呈现链状，空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关，空间复杂度为 O(log N)。
112 Path Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
return preorder(root,0,targetSum);
}
int preorder(TreeNode* root,int sum,int targetSum){
if(root){
sum+=root->val;
if(!root->left && !root->right){
if(sum==targetSum) return true;
}
return preorder(root->left,sum,targetSum) || preorder(root->right,sum,targetSum);
}
return false;
}
};
|
OR
1
2
3
4
5
6
7
8
9
10
|
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root==nullptr) return false;
if(root->left==nullptr && root->right==nullptr){
return targetSum==root->val;
}
return hasPathSum(root->left,targetSum-root->val) || hasPathSum(root->right,targetSum-root->val);
}
};
|
113 Path Sum II
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<vector<int>> res;
vector<int> path;
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
dfs(root,targetSum);
return res;
}
void dfs(TreeNode* root,int targetSum){
if(root){
path.push_back(root->val);
if(!root->left && !root->right){
if(targetSum==root->val){
res.push_back(path);
}
}
dfs(root->left,targetSum-root->val);
dfs(root->right,targetSum-root->val);
path.pop_back();
}
return;
}
};
|
OR
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>> ret;
vector<int> path;
void dfs(TreeNode* root,int targetSum){
if(root==nullptr) return;
path.push_back(root->val);
targetSum-=root->val;
if(root->left==nullptr && root->right==nullptr && targetSum==0){
ret.push_back(path);
}
dfs(root->left,targetSum);
dfs(root->right,targetSum);
path.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
dfs(root,targetSum);
return ret;
}
};
|
437 Path Sum III
DFS
- 时间复杂度：O(n^2) 两重遍历
- 空间复杂度：O(n)
前缀和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
unordered_map<long long,int> frequency;
int pathSum(TreeNode* root, int targetSum) {
frequency[0]=1;
return dfs(root,targetSum,0);
}
int dfs(TreeNode* root,int targetSum,long long curSum){
if(!root) return 0;
curSum+=root->val;
int count=frequency[curSum-targetSum];
frequency[curSum]+=1;
count+=dfs(root->left,targetSum,curSum);
count+=dfs(root->right,targetSum,curSum);
frequency[curSum]-=1;
return count;
}
};
|
101 Symmetric Tree
recursive
如果同时满足下面的条件，两个树互为镜像：
- 它们的两个根结点具有相同的值
- 每个树的
右子树都与另一个树的左子树镜像对称
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root==nullptr) return true;
return check(root->left,root->right);
}
bool check(TreeNode* left,TreeNode* right){
if(left==nullptr && right==nullptr) return true;
if(left==nullptr || right==nullptr) return false;
return left->val==right->val && check(left->left,right->right) && check(left->right,right->left);
}
};
|
iterative: queue
初始化时把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
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) {
if(root==nullptr) return true;
queue<TreeNode*> q;
q.push(root);
q.push(root);
while(!q.empty()){
TreeNode* left=q.front();
q.pop();
TreeNode* right=q.front();
q.pop();
if(left==nullptr && right==nullptr) continue;
if(left==nullptr || right==nullptr) return false;
if(left->val!=right->val) return false;
q.push(left->left);
q.push(right->right);
q.push(left->right);
q.push(right->left);
}
return true;
}
};
|
110 Balanced Binary Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(!root) return true;
int left=getHeight(root->left);
int right=getHeight(root->right);
if(abs(left-right)<=1) return isBalanced(root->left) && isBalanced(root->right);
return false;
}
int getHeight(TreeNode* root){
if(root==nullptr) return 0;
return max(getHeight(root->left),getHeight(root->right))+1;
}
};
|
114 Flatten Binary Tree to Linked List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public:
void flatten(TreeNode* root) {
if(!root) return;
flatten(root->left);
flatten(root->right);
if(root->left==nullptr) return;
//将left-subtree插入到root和root->right之间
TreeNode* p=root->left;
//left-subtree的最后一个结点
while(p->right){
p=p->right;
}
p->right=root->right;
root->right=root->left;
root->left=nullptr;
}
};
|
利用preorder，每遍历一个节点，就将上一个节点的右指针更新为当前节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
void flatten(TreeNode* root) {
if(!root) return;
stack<TreeNode*> stk;
stk.push(root);
TreeNode* prev=nullptr;
while(!stk.empty()){
TreeNode* node=stk.top();
stk.pop();
if(prev){
prev->left=nullptr;
//利用preorder，每遍历一个节点，就将上一个节点的右指针更新为当前节点。
prev->right=node;
}
if(node->right) stk.push(node->right);
if(node->left) stk.push(node->left);
prev=node;
}
}
};
|
116 Populating Next Right Pointers in Each Node
Iterative
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:
Node* connect(Node* root) {
if(!root) return root;
Node* node=root;
queue<Node*> q;
q.push(node);
while(!q.empty()){
int size=q.size();
Node* prev;
for(int i=0;i<size;i++){
Node* cur=q.front();
q.pop();
if(i==0){
prev=cur;
}else{
prev->next=cur;
prev=prev->next;
}
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
prev->next=nullptr;
}
return 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:
Node* connect(Node* root) {
if(!root) return root;
queue<Node*> q;
q.push(root);
while(!q.empty()){
int size=q.size();
for(int i=0;i<size;i++){
Node* cur=q.front();
q.pop();
if(i!=size-1){
cur->next=q.front();
}
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
}
return root;
}
};
|
Recursive
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
Node* connect(Node* root) {
if(!root) return root;
dfs(root);
return root;
}
void dfs(Node* root){
if(!root) return;
Node* left=root->left;
Node* right=root->right;
while(left!=nullptr){
left->next=right;
left=left->right;
right=right->left;
}
dfs(root->left);
dfs(root->right);
}
};
|
- 时间复杂度：O(n)
- 空间复杂度：
- O(1)
- The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.
117 Populating Next Right Pointers in Each Node II
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:
Node* connect(Node* root) {
if(!root) return root;
Node* cur=root;
while(cur){
Node* dummy=new Node(0);
Node* pre=dummy;
while(cur){
if(cur->left!=nullptr){
pre->next=cur->left;
pre=pre->next;
}
if(cur->right!=nullptr){
pre->next=cur->right;
pre=pre->next;
}
cur=cur->next;
}
cur=dummy->next;
}
return root;
}
};
|
二叉树的BFS
Level Order
107 Binary Tree Level Order Traversal II
iterative
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<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
if(root==nullptr) return res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int size=q.size();
vector<int> temp;
for(int i=0;i<size;i++){
TreeNode* cur=q.front();
q.pop();
temp.push_back(cur->val);
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
res.push_back(temp);
}
reverse(res.begin(),res.end());
return res;
}
};
|
注意：要有if(root==nullptr) return res;，否则会Runtime Error: runtime error: member access within null pointer of type ‘TreeNode’ (solution.cpp)
recursive
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>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
if(root==nullptr) return res;
levelorder(root,res,0);
reverse(res.begin(),res.end());
return res;
}
void levelorder(TreeNode* root,vector<vector<int>>& res,int level){
if(root==nullptr) return;
if(level>=res.size()){
res.push_back(vector<int>());
}
res[level].push_back(root->val);
levelorder(root->left,res,level+1);
levelorder(root->right,res,level+1);
}
};
|
103 Binary Tree Zigzag Level Order Traversal
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<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root==nullptr) return res;
queue<TreeNode*> q;
q.push(root);
bool left_to_right=true;
while(!q.empty()){
int size=q.size();
vector<int> temp;
for(int i=0;i<size;i++){
TreeNode* cur=q.front();
q.pop();
temp.push_back(cur->val);
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
if(!left_to_right){
reverse(temp.begin(),temp.end());
}
left_to_right=!left_to_right;
res.push_back(temp);
}
return res;
}
};
|
left_to_right=!left_to_right;的写法很妙。
Morris Traversal
Inorder
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
|
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode* current=root;
while(current){
//left is null then print the node and go to right
if(current->left==nullptr){
res.push_back(current->val);
current=current->right;
}else{
//find the predecessor
TreeNode* predecessor=current->left;
//to find predecessor keep going right
//till right node is not null or right node is not current
while(predecessor->right!=current && predecessor->right!=nullptr){
predecessor=predecessor->right;
}
//if right node is null then go left
//after establishing link from predecessor to current
if(predecessor->right==nullptr){
predecessor->right=current;
current=current->left;
}else{
//left is already visit.
//go right after visiting current.
predecessor->right=nullptr;
res.push_back(current->val);
current=current->right;
}
}
}
return res;
}
};
|
Preorder
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
|
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode* current=root;
while(current){
//left is null then print the node and go to right
if(current->left==nullptr){
res.push_back(current->val);
current=current->right;
}else{
//find the predecessor
TreeNode* predecessor=current->left;
//to find predecessor keep going right
//till right node is not null or right node is not current
while(predecessor->right!=current && predecessor->right!=nullptr){
predecessor=predecessor->right;
}
//if right node is null then go left
//after establishing link from predecessor to current
if(predecessor->right==nullptr){
predecessor->right=current;
res.push_back(current->val);
current=current->left;
}else{
//left is already visit.
//go right after visiting current.
predecessor->right=nullptr;
current=current->right;
}
}
}
return res;
}
};
|
二叉搜索树BST
99 Recover Binary Search Tree
注意认真读题：the values of exactly two nodes of the tree were swapped by mistake “恰好两个节点”
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:
void recoverTree(TreeNode* root) {
stack<TreeNode*> stk;
TreeNode* cur=root;
//exactly two nodes
TreeNode *x=nullptr,*y=nullptr,*pred=nullptr;
while(!stk.empty() || cur){
while(cur){
stk.push(cur);
cur=cur->left;
}
cur=stk.top();
stk.pop();
if(pred && cur->val<pred->val){
y=cur;
if(x==nullptr){
x=pred;
}else{
break;
}
}
pred=cur;
cur=cur->right;
}
swap(x->val,y->val);
}
};
|
注意：TreeNode *x=nullptr,*y=nullptr,*pred=nullptr;这里都要初始化为nullptr，否则会Wrong Answer。
- 时间复杂度：O(n)
- 空间复杂度：O(H=logn)
897 Increasing Order Search Tree
Recursive
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
vector<int> res;
TreeNode* increasingBST(TreeNode* root) {
inorder(root);
TreeNode* dummyNode=new TreeNode(-1);
TreeNode* cur=dummyNode;
for(int x:res){
cur->right=new TreeNode(x);
cur=cur->right;
}
return dummyNode->right;
}
void inorder(TreeNode* root){
if(root==nullptr) return;
inorder(root->left);
res.push_back(root->val);
inorder(root->right);
}
};
|
OR
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
TreeNode* res;
TreeNode* increasingBST(TreeNode* root) {
TreeNode* dummyNode=new TreeNode(-1);
res=dummyNode;
inorder(root);
return dummyNode->right;
}
void inorder(TreeNode* root){
if(root==nullptr) return;
inorder(root->left);
//inorder过程中修改节点指向
res->right=root;
root->left=nullptr;
res=root;
inorder(root->right);
}
};
|
Iterative(Stack)
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:
TreeNode* increasingBST(TreeNode* root) {
TreeNode* first=nullptr;
TreeNode* prev=nullptr;
TreeNode* cur=root;
stack<TreeNode*> stk;
while(!stk.empty() || cur){
while(cur){
stk.push(cur);
cur=cur->left;
}
cur=stk.top();
stk.pop();
if(prev==nullptr){
first=cur;
}else{
prev->right=cur;
}
prev=cur;
cur->left=nullptr;
cur=cur->right;
}
return first;
}
};
|
只需要在中序遍历的过程中维护上一个访问的节点prev和当前访问的节点cur。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
stack<TreeNode*> stk;
TreeNode *prev=nullptr,*cur=root;
while(!stk.empty() || cur){
while(cur){
stk.push(cur);
cur=cur->left;
}
cur=stk.top();
stk.pop();
if(prev==p){
return cur;
}
prev=cur;
cur=cur->right;
}
return nullptr;
}
};
|
OR
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
TreeNode* cur=root;
TreeNode* res=nullptr;
while(cur){
if(cur->val>p->val){
res=cur;
cur=cur->left;
}else{
cur=cur->right;
}
}
return res;
}
};
|
538 Convert BST to Greater Tree
反序Inorder(Iterative)
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* convertBST(TreeNode* root) {
stack<TreeNode*> stk;
TreeNode* cur=root;
int sum=0;
while(!stk.empty() || cur){
while(cur){
stk.push(cur);
cur=cur->right;
}
cur=stk.top();
stk.pop();
sum+=cur->val;
cur->val=sum;
cur=cur->left;
}
return root;
}
};
|
反序Inorder(Recursive)
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
int sum=0;
TreeNode* convertBST(TreeNode* root) {
if(!root) return root;
convertBST(root->right);
sum+=root->val;
root->val=sum;
convertBST(root->left);
return root;
}
};
|
173 Binary Search Tree Iterator
Recursive
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 BSTIterator {
public:
vector<int> res;
int cur;
BSTIterator(TreeNode* root) {
cur=0;
inorder(root);
}
void inorder(TreeNode* root){
if(!root) return;
inorder(root->left);
res.push_back(root->val);
inorder(root->right);
}
int next() {
return res[cur++];
}
bool hasNext() {
return cur<res.size();
}
};
|
- 时间复杂度：初始化O(n)，每次调用O(1)
- 空间复杂度：O(n)
Iterative
通过迭代的方式对二叉树做中序遍历。此时无需预先计算出中序遍历的全部结果，只需要实时维护当前栈的情况即可。
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 BSTIterator {
public:
stack<TreeNode*> stk;
TreeNode* cur;
BSTIterator(TreeNode* root):cur(root) {
}
int next() {
while(cur){
stk.push(cur);
cur=cur->left;
}
cur=stk.top();
stk.pop();
int res=cur->val;
cur=cur->right;
return res;
}
bool hasNext() {
return cur!=nullptr || !stk.empty();
}
};
|
- 时间复杂度：初始化和每次调用O(1)
- 空间复杂度：O(n)
HashTable哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
stack<TreeNode*> stk;
unordered_set<int> hashTable;
while(!stk.empty() || root){
while(root){
stk.push(root);
root=root->left;
}
root=stk.top();
stk.pop();
if(hashTable.count(k-root->val)){
return true;
}
hashTable.insert(root->val);
root=root->right;
}
return false;
}
};
|
Two Pointers双指针
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
|
class Solution {
public:
TreeNode *getLeft(stack<TreeNode *> &stk) {
TreeNode *root = stk.top();
stk.pop();
TreeNode *node = root->right;
while (node != nullptr) {
stk.push(node);
node = node->left;
}
return root;
}
TreeNode *getRight(stack<TreeNode *> &stk) {
TreeNode *root = stk.top();
stk.pop();
TreeNode *node = root->left;
while (node != nullptr) {
stk.push(node);
node = node->right;
}
return root;
}
bool findTarget(TreeNode *root, int k) {
TreeNode *left = root, *right = root;
stack<TreeNode *> leftStack, rightStack;
leftStack.push(left);
while (left->left != nullptr) {
leftStack.push(left->left);
left = left->left;
}
rightStack.push(right);
while (right->right != nullptr) {
rightStack.push(right->right);
right = right->right;
}
while (left != right) {
if (left->val + right->val == k) {
return true;
}
if (left->val + right->val < k) {
left = getLeft(leftStack);
} else {
right = getRight(rightStack);
}
}
return false;
}
};
|
96 Unique Binary Search Trees
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
int numTrees(int n) {
vector<int> numTree(n+1);
numTree[0]=1;
numTree[1]=1;
for(int node=2;node<=n;node++){
int total=0;
for(int root=1;root<=node;root++){
total+=numTree[root-1]*numTree[node-root];
}
numTree[node]=total;
}
return numTree[n];
}
};
|
数学——卡特兰数
1
2
3
4
5
6
7
8
9
10
|
class Solution {
public:
int numTrees(int n) {
long long C = 1;
for (int i = 0; i < n; ++i) {
C = C * 2 * (2 * i + 1) / (i + 2);
}
return (int)C;
}
};
|
TreeSet + TreeMap
217 Contains Duplicate
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> s;
for(int num:nums){
if(s.count(num)){
return true;
}
s.insert(num);
}
return false;
}
};
|
219 Contains Duplicate II
HashTable
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int,int> numToIndex;
int n=nums.size();
for(int i=0;i<n;i++){
int num=nums[i];
if(numToIndex.count(num) && i-numToIndex[num]<=k){
return true;
}
numToIndex[num]=i;
}
return false;
}
};
|
Sliding Window + HashTable
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> s;
int n=nums.size();
for(int i=0;i<n;i++){
if(i>k){
s.erase(nums[i-k-1]);
}
if(s.count(nums[i])){
return true;
}
s.insert(nums[i]);
}
return false;
}
};
|
220 Contains Duplicate III
Sliding Window + HashTable
逐一扫描数组中的每个数字。对于每个数字nums[i]，应该先从它前面的k个数字中找出小于或等于nums[i]的最大的数字，如果这个数字与nums[i]的差的绝对值不大于t，那么就找到了一组符合条件的两个数字。否则，再从它前面的k个数字中找出大于或等于nums[i]的最小的数字，如果这个数字与nums[i]的差的绝对值不大于t，就找到了一组符合条件的两个数字。
TreeSet源码：
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
|
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
/**
* The backing map.
*/
private transient NavigableMap<E,Object> m;
public E lower(E e) {
return m.lowerKey(e);
}
public E floor(E e) {
return m.floorKey(e);
}
public E ceiling(E e) {
return m.ceilingKey(e);
}
public E higher(E e) {
return m.higherKey(e);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
|
public interface NavigableMap<K,V> extends SortedMap<K,V> {
//Returns the greatest key strictly less than the given key, or null if there is no such key.
K lowerKey(K key);
//Returns the greatest key less than or equal to the given key, or null if there is no such key.
K floorKey(K key);
//Returns the least key greater than or equal to the given key, or null if there is no such key.
K ceilingKey(K key);
//Returns the least key strictly greater than the given key, or null if there is no such key.
K higherKey(K key);
...
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
//用TreeSet来保存每个数字nums[i]前面的k个数字
TreeSet<Long> st=new TreeSet<>();
int n=nums.length;
for(int i=0;i<n;i++){
if(i>indexDiff){
st.remove((long)nums[i-indexDiff-1]);
}
Long lower=st.floor((long)nums[i]);
if(lower!=null && lower>=(long)nums[i]-valueDiff) return true;
Long upper=st.ceiling((long)nums[i]);
if(upper!=null && upper<=(long)nums[i]+valueDiff) return true;
st.add((long)nums[i]);
}
return false;
}
}
|
if nums[i]-lower<=valueDiff return true;
但小于或等于nums[i]的最大的数字即floor返回值为对象类型，为了计算方便，转换为：
if lower>=nums[i]-valueDiff return true;
同理，if upper-nums[i]<=valueDiff return true; 可以转换为：
if upper<=num[i]+valueDiff return 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 boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
//用TreeSet来保存每个数字nums[i]前面的k个数字
TreeSet<Long> st=new TreeSet<>();
int n=nums.length;
for(int i=0;i<n;i++){
if(i>indexDiff){
st.remove((long)nums[i-indexDiff-1]);
}
Long num=nums[i]*1L;
Long lower=st.floor((long)nums[i]);
if(lower!=null && num-lower<=valueDiff) return true;
Long upper=st.ceiling((long)nums[i]);
if(upper!=null && upper-num<=valueDiff) return true;
st.add(num);
}
return false;
}
}
|
- 时间复杂度：O(nlogk)
- 空间复杂度：O(k)
Bucket
由于这个题目关心的是差的绝对值小于或等于valueDiff的数字，因此可以将数字放入若干大小为valueDiff+1的桶中。例如，将从0到valueDiff的数字放入编号为0的桶中，从valueDiff+1到2valueDiff+1的数字放入编号为1的桶中。其他数字以此类推。这样做的好处是如果两个数字被放入同一个桶中，那么它们的差的绝对值一定小于或等于valueDiff。
还是逐一扫描数组中的数字。如果当前扫描到数字num，那么它将放入编号为id的桶中。如果这个桶中之前已经有数字，那么就找到两个差的绝对值小于或等于t的数字。如果桶中之前没有数字，则再判断编号为id-1和id-2的这两个相邻的桶中是否存在与num的差的绝对值小于或等于t的数字。因为其他桶中的数字与num的差的绝对值一定大于t，所以不需要判断其他的桶中是否有符合条件的数字。
bool containsNearbyAlmostDuplicate(vector <int> & nums, int k, int t)
1、为什么 bucketSize 需要对 t 进行 +1 操作
目的是为了确保绝对值小于等于 t 的数能够落到一个桶中。举个🌰，假设 [0,1,2,3]，t = 3，显然四个数都应该落在一个桶。
如果不对 t 进行 +1 操作的话，那么 [0,1,2] 和 [3] 会被落到不同的桶中，那么为了能让他们落到同一桶中，需要对 t 进行加一操作。
这样我们的数轴就能被分割成：
1
|
0 1 2 3 | 4 5 6 7 | 8 9 10 11 | 12 …
|
总结一下，size = t + 1 的本质是因为差值为 t 两个数在数轴上相隔距离为 t + 1，它们需要被落到同一个桶中。
当有了 bucketSize 之后，对于正数部分则有 id = num / bucketSize。
2、如何理解负数部分的逻辑？
由于处理正数的时候，处理了 0即num>=0，因此负数部分是从 -1 开始的。
而且此时有 t = 3 和 bucketSize = t + 1 = 4。考虑🌰，[-4 -3 -2 -1]（它们应该落在一个桶中）
如果直接复用 id = num / bucketSize 的话，[-4] 和 [-3,-2,-1] 会被分到不同的桶中。
1
2
3
4
|
-4/4=-1
-3/4=0
-2/4=0
-1/4=0
|
根本原因是我们处理整数的时候，已经分掉了 0。
因此这时候我们需要先对 num 进行 +1 操作（即将负数部分在数轴上进行整体右移），即得到 (num +1) / bucketSize。
1
2
3
4
|
(-4+1)/4=0
(-3+1)/4=0
(-2+1)/4=0
(-1+1)/4=0
|
这样就可以将负数部分与正数部分一样，可以被正常分割了。
但是由于 0 号桶已经被使用了，我们需要再在此基础上再 -1，相当于桶数轴（id）往左移，即得到 (num +1) / size - 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
|
class Solution {
public:
int getBucketId(int num,int bucketSize){
return num>=0?num/bucketSize:(num+1)/bucketSize-1;
}
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
unordered_map<int,int> mp;
int n=nums.size();
int bucketSize=valueDiff+1;
for(int i=0;i<n;i++){
if(i>indexDiff){
mp.erase(getBucketId(nums[i-indexDiff-1],bucketSize));
}
int num=nums[i];
int id=getBucketId(num,bucketSize);
if(mp.find(id)!=mp.end()) return true;
if(mp.find(id-1)!=mp.end() && num-mp[id-1]<=valueDiff) return true;
if(mp.find(id+1)!=mp.end() && mp[id+1]-num<=valueDiff) return true;
mp[id]=num;
}
return false;
}
};
|
729 My Calendar I
直接遍历
对于两个区间 [left,right) 和 [start,end)，如果二者没有交集，则应该满足：
start>=right || left>=end
这意味着如果满足start<right && left<end，则二者会产生交集，直接返回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 MyCalendar {
public:
vector<pair<int,int>> booked;
MyCalendar() {
}
bool book(int start, int end) {
for(auto &[left,right]:booked){
if(start<right && left<end){
return false;
}
}
booked.emplace_back(start,end);
return true;
}
};
/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar* obj = new MyCalendar();
* bool param_1 = obj->book(start,end);
*/
|
TreeMap
如果待添加的事项占用的时间区间是[m，n），就需要找出开始时间小于m的所有事项中开始最晚的一个，以及开始时间大于m的所有事项中开始最早的一个。如果待添加的事项和这两个事项都没有重叠，那么该事项可以添加在日程表中。
每当添加一个新的开始时间为start、结束时间为end的时间区间时，就调用函数floorEntry查找日程表中开始时间小于start的最后一个时间区间，如果该时间区间的结束时间大于start，则表明该时间区间与待添加的时间区间重叠。
接着调用函数ceilingEntry查找日程表中开始时间大于start的第1个时间区间，如果该时间区间的开始时间比end还要早，则表明这两个时间区间重叠。
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
|
class MyCalendar {
TreeMap<Integer,Integer> events;
public MyCalendar() {
events=new TreeMap<>();
}
public boolean book(int start, int end) {
Map.Entry<Integer,Integer> before=events.floorEntry(start);
if(before!=null && before.getValue()>start) return false;
Map.Entry<Integer,Integer> after=events.ceilingEntry(start);
if(after!=null && after.getKey()<end) return false;
events.put(start,end);
return true;
}
}
/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar obj = new MyCalendar();
* boolean param_1 = obj.book(start,end);
*/
|
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
Trie
前缀树，又称为字典树，它用一个树状的数据结构存储一个字典中的所有单词。
前缀树的根节点不表示任何字符。
字符串在前缀树中的路径并不一定终止于叶节点。
如果前缀树路径到达某个节点时它表示了一个完整的字符串，那么字符串最后一个字符对应的节点有特殊的标识。例如，图中字符串最后一个字符对应的节点都用灰色背景标识。
208 Implement Trie (Prefix Tree)
分析：首先定义前缀树中节点的数据结构。前缀树中的节点对应字符串中的一个字符。如果只考虑英文小写字母，那么字符可能是从’a’到’z’的任意一个，因此前缀树中的节点可能有26个子节点。可以将26个子节点放到一个数组中，数组中的第1个元素是对应字母’a’的子节点，第2个元素是对应字母’b’的子节点，其余的以此类推。
值得注意的是，前缀树的节点中没有一个字段表示节点对应的字符。这是因为可以通过节点是其父节点的第几个子节点得知它对应的字符，也就没有必要在节点中添加一个字段。
节点中还需要一个布尔类型的字段表示到达该节点的路径对应的字符串是否为字典中一个完整的单词。
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
|
class Trie {
private:
//0:'a' 1:'b' ...
vector<Trie*> children;
bool isWord;
public:
Trie():children(26),isWord(false) {
}
void insert(string word) {
Trie* node=this;
for(char ch:word){
if(node->children[ch-'a']==nullptr){
node->children[ch-'a']=new Trie();
}
node=node->children[ch-'a'];
}
node->isWord=true;
}
bool search(string word) {
Trie* node=this;
for(char ch:word){
if(node->children[ch-'a']==nullptr){
return false;
}
node=node->children[ch-'a'];
}
return node->isWord;
}
bool startsWith(string prefix) {
Trie* node=this;
for(char ch:prefix){
if(node->children[ch-'a']==nullptr){
return false;
}
node=node->children[ch-'a'];
}
return true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
|
- 时间复杂度：初始化为 O(1)，函数insert、search和startWith的时间复杂度都是O(n)
- 空间复杂度：O(|T|Σ)，其中 |T| 为所有插入字符串的长度之和，Σ 为字符集的大小，本题 Σ=26
648 Replace Words
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
|
struct Trie
{
private:
vector<Trie *> children;
bool isWord;
public:
Trie() : children(26), isWord(false) {}
Trie *buildTrie(vector<string> &dictionary)
{
Trie *root = this;
for (string str : dictionary)
{
Trie *node = root;
for (char ch : str)
{
if (node->children[ch - 'a'] == nullptr)
{
node->children[ch - 'a'] = new Trie();
}
node = node->children[ch - 'a'];
}
node->isWord = true;
}
return root;
}
string search(Trie *root, string &str)
{
Trie *node = root;
string res;
for (char ch : str)
{
if (node->children[ch - 'a'] == nullptr || node->isWord)
{
break;
}
res += ch;
node = node->children[ch - 'a'];
}
return node->isWord ? res : str;
}
};
class Solution {
public:
vector<string> split(string sentence)
{
int i;
int start = 0;
string str;
vector<string> res;
for (i = 0; i < sentence.length(); i++)
{
if (sentence[i] == ' ')
{
// substr(pos,n)
str = sentence.substr(start, i - start);
res.push_back(str);
start = i + 1;
}
}
str = sentence.substr(start, i - start);
res.push_back(str);
return res;
}
string replaceWords(vector<string> &dictionary, string sentence)
{
Trie *trie = new Trie();
Trie *root = trie->buildTrie(dictionary);
vector<string> v;
v=split(sentence);
for(string& s : v){
s=trie->search(trie,s);
}
string res;
for (int i = 0; i < v.size() - 1; i++)
{
res+=(v[i] + " ");
}
res += v.back();
return res;
}
};
|
- 时间复杂度：O(d + s)。其中 d 是 dictionary 的字符数，s 是 sentence 的字符数。构建字典树消耗 O(d) 时间，每个单词搜索前缀均消耗线性时间。
- 空间复杂度：O(d + s)，构建哈希集合消耗 O(d)空间，分割 sentence 消耗 O(s) 空间。
676 Implement Magic Dictionary
bool search(String searchWord)Returns true if you can change exactly one character in searchWord to match any string in the data structure, otherwise returns false.
字典树
可以根据深度优先的顺序搜索前缀树的每条路径。如果到达的节点与字符串中的字符不匹配，则表示此时修改了字符串中的一个字符以匹配前缀树中的路径。如果到达对应字符串最后一个字符对应的节点时该节点的isWord字段的值为true，而且此时正好修改了字符串中的一个字符，那么就找到了修改字符串中一个字符对应的路径，符合题目的条件，可以返回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
|
struct Trie{
vector<Trie*> children;
bool isWord;
Trie():children(26),isWord(false){}
};
class MagicDictionary {
public:
Trie* root;
MagicDictionary() {
root=new Trie();
}
void buildDict(vector<string> dictionary) {
for(string str:dictionary){
Trie* node=root;
for(char ch:str){
if(node->children[ch-'a']==nullptr){
node->children[ch-'a']=new Trie();
}
node=node->children[ch-'a'];
}
node->isWord=true;
}
}
bool search(string searchWord) {
return dfs(root,searchWord,0,0);
}
bool dfs(Trie* root,string word,int index,int edit){
if(root==nullptr) return false;
if(root->isWord && index==word.length() && edit==1) return true;
if(index<word.length() && edit<=1){
bool found=false;
for(int j=0;j<26 && !found;j++){
int next=(j==word[index]-'a'?edit:edit+1);
found=dfs(root->children[j],word,index+1,next);
}
return found;
}
return false;
}
};
|
n 是数组 dictionary 的长度，m 是数组 dictionary 中字符串的平均长度。
Fuzzy Match
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 MagicDictionary {
public:
unordered_map<string,unordered_set<char>> dict;
MagicDictionary() {
dict.clear();
}
void buildDict(vector<string> dictionary) {
for(string& str:dictionary){
for(int i=0;i<str.length();i++){
char temp=str[i];
str[i]='*';
dict[str].insert(temp);
str[i]=temp;
}
}
}
bool search(string searchWord) {
for(int i=0;i<searchWord.length();i++){
char temp=searchWord[i];
searchWord[i]='*';
if(dict.count(searchWord)){
const auto& char_set=dict[searchWord];
if(char_set.count(temp)==0 || char_set.size()>1){
return true;
}
}
searchWord[i]=temp;
}
return false;
}
};
|
其实这道题坑还挺多的。
例如：如果dictionary中有[“hello”,“hallo”,……]，如果查询"hello”，结果应该返回true。
所以search中的逻辑判断为char_set.count(temp)==0 || char_set.size()>1，两者用 || 连接，并且缺一不可。
-
时间复杂度：
BuildDict: O(nm)
Search: O(m)
820 Short Encoding of Words
由于在最短编码之中出现的每个单词之后都有一个字符’＃’，因此计算长度时出现的每个单词的长度都要加1。在前缀树中统计路径长度时，可以统计从根节点到每个叶节点的路径的长度。前缀树的根节点并不对应单词的任何字符，在统计路径时将根节点包括进去相当于将单词的长度加1。通常用DFS的算法统计路径的长度。
677 Map Sum Pairs
421 Maximum XOR of Two Numbers in an Array
NeetCode-Tree
100 Same Tree
1
2
3
4
5
6
7
8
9
|
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==nullptr && q==nullptr) return true;
if(p==nullptr || q==nullptr) return false;
if(p->val!=q->val) return false;
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
};
|
- 时间复杂度：O(min(m,n))
- 空间复杂度：O(min(m,n))
226 Invert Binary Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return root;
TreeNode* temp=root->left;
root->left=root->right;
root->right=temp;
invertTree(root->left);
invertTree(root->right);
return root;
}
};
|
从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return root;
TreeNode* left=invertTree(root->left);
TreeNode* right=invertTree(root->right);
root->left=right;
root->right=left;
return root;
}
};
|
124 Binary Tree Maximum Path Sum
Notice:
A node can only appear in the sequence at most once.
Note that the path does not need to pass through the root.
-1000 <= Node.val <= 1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
int maxSum=INT_MIN;
int maxPathSum(TreeNode* root) {
oneSideSum(root);
return maxSum;
}
int oneSideSum(TreeNode* root){
if(!root) return 0;
int leftMax=oneSideSum(root->left);
int rightMax=oneSideSum(root->right);
//leftMax,rightMAx maybe negative
leftMax=max(leftMax,0);
rightMax=max(rightMax,0);
//compute max path sum with split
maxSum=max(maxSum,root->val+leftMax+rightMax);
//compute max path sum without split
return root->val+max(leftMax,rightMax);
}
};
|
helper returns maxpathsum without splitting branches, inside helper we also update maxSum by computing maxpathsum with a split;
102 Binary Tree Level Order Traversal
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<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root) return res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int size=q.size();
vector<int> temp;
while(size--){
TreeNode* cur=q.front();
q.pop();
temp.push_back(cur->val);
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
res.push_back(temp);
}
return res;
}
};
|
注意：层序遍历要加这样一行代码：
if(!root) return res;
否则会有Runtime Error：
Line 24: Char 37: runtime error: member access within null pointer of type ‘TreeNode’ (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:33:37
572 Subtree of Another Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(!root && !subRoot) return true;
if(!root || !subRoot) return false;
return isSameTree(root,subRoot) || isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}
bool isSameTree(TreeNode* p,TreeNode* q){
if(p==nullptr && q==nullptr) return true;
if(p==nullptr || q==nullptr) return false;
return p->val==q->val && isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
};
|
- 时间复杂度：O(|root|*|subRoot|)
- 空间复杂度：O(max{root,subRoot})
105 Construct Binary Tree from Preorder and Inorder Traversal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
unordered_map<int,int> mp;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for(int i=0;i<inorder.size();i++){
mp[inorder[i]]=i;
}
return build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
}
TreeNode* build(vector<int>& preorder,int preLeft,int preRight,vector<int>& inorder,int inLeft,int inRight){
if(preLeft>preRight || inLeft>inRight) return nullptr;
int rootValue=preorder[preLeft];
TreeNode* root=new TreeNode(rootValue);
int mid=mp[rootValue];
int numLeft=mid-inLeft;
root->left=build(preorder,preLeft+1,preLeft+numLeft,inorder,inLeft,mid-1);
root->right=build(preorder,preLeft+numLeft+1,preRight,inorder,mid+1,inRight);
return root;
}
};
|
230 Kth Smallest Element in a BST
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> stk;
while(!stk.empty() || root){
while(root){
stk.push(root);
root=root->left;
}
root=stk.top();
stk.pop();
k--;
if(k==0){
break;
}
root=root->right;
}
return root->val;
}
};
|
211 Design Add and Search Words Data Structure
212 Word Search II