- 科技
- LeetCode笔记（树，dp：状态机）
965 - 107 - 309。
965. 单值二叉树
class Solution
{
bool
checkValid(TreeNode
* root
, int prev
) {
if(root
== nullptr
) return true
;
if(root
->val
!= prev
) return false
;
bool left
= checkValid(root
->left
, prev
);
bool right
= checkValid(root
->right
, prev
);
return left
&& right
;
}
public
:
bool
isUnivalTree(TreeNode
* root
) {
if(root
== nullptr
) return true
;
return checkValid(root
, root
->val
);
}
};
107. 二叉树的层次遍历 II
就普通层序遍历一下，最后反转就可以了
class Solution
{
public
:
vector
<vector
<int>> levelOrderBottom(TreeNode
* root
) {
if(root
== nullptr
) return {};
vector
<vector
<int>> res
;
queue
<TreeNode
*> que
;
que
.push(root
);
while(!que
.empty()) {
int size
= que
.size();
vector
<int> level
;
for(int i
= 0; i
< size
; i
++) {
TreeNode
* tmp
= que
.front(); que
.pop();
level
.push_back(tmp
->val
);
if(tmp
->left
) que
.push(tmp
->left
);
if(tmp
->right
) que
.push(tmp
->right
);
}
res
.push_back(level
);
}
reverse(res
.begin(), res
.end());
return res
;
}
};
309. 最佳买卖股票时机含冷冻期
class Solution
{
public
:
int maxProfit(vector
<int>& prices
) {
if(prices
.size() < 1) return 0;
vector
<vector
<int>> status(3, vector
<int>(prices
.size(), 0));
status
[0][0] = -prices
[0];
status
[1][0] = status
[2][0] = 0;
for(int i
= 1; i
< prices
.size(); i
++) {
status
[0][i
] = max(status
[0][i
- 1], status
[1][i
- 1] - prices
[i
]);
status
[1][i
] = max(status
[1][i
- 1], status
[2][i
- 1]);
status
[2][i
] = status
[0][i
- 1] + prices
[i
];
}
return max(status
[1].back(), status
[2].back());
}
};
Processed:
0.019, SQL:
8
