比较简单，不多赘述，特殊的会进行一些笔记
144. 二叉树的前序遍历 - 力扣（LeetCode）class Solution {
public:
vectorans;
void DFS(TreeNode* root){
if(root==nullptr)return;
ans.emplace_back(root->val);
DFS(root->left);
DFS(root->right);
}
vector preorderTraversal(TreeNode* root) {
DFS(root);
return ans;
}
};
94. 二叉树的中序遍历 - 力扣（LeetCode）
class Solution {
public:
vectorans;
vector inorderTraversal(TreeNode* root) {
if(root==nullptr){
return {};
}
if(root->left){
inorderTraversal(root->left);
}
ans.push_back(root->val);
if(root->right){
inorderTraversal(root->right);
}
return ans;
}
};
145. 二叉树的后序遍历 - 力扣（LeetCode）
class Solution {
public:
vectorans;
void DFS(TreeNode* root){
if(root==nullptr)return;
DFS(root->left);
DFS(root->right);
ans.push_back(root->val);
}
vector postorderTraversal(TreeNode* root) {
DFS(root);
return ans;
}
};
589. N 叉树的前序遍历 - 力扣（LeetCode）
class Solution {
public:
vectorv;
void DFS(Node* root){
if(root==nullptr)return;
v.push_back(root->val);
for(auto x:root->children){
DFS(x);
}
}
vector preorder(Node* root) {
DFS(root);
return v;
}
};
590. N 叉树的后序遍历 - 力扣（LeetCode）
这题有个小细节值得注意的，之前我习惯声明一个全局的vector来保存结果，这里的方法将vector作为参数传入函数中，并赋为引用，以实时修改vector的内容。
class Solution {
public:
void helper(const Node* root, vector & res) {
if (root == nullptr) {
return;
}
for (auto & ch : root->children) {
helper(ch, res);
}
res.emplace_back(root->val);
}
vector postorder(Node* root) {
vector res;
helper(root, res);
return res;
}
};
2.遍历相关-BFS
637. 二叉树的层平均值 - 力扣（LeetCode）
class Solution {
public:
vectorv;
void BFS(TreeNode* root){
queueq;
q.push(root);
while(!q.empty()){
int n=q.size();
long long sum=0.0;
for(int i=0;ival;
if(temp->left)q.push(temp->left);
if(temp->right)q.push(temp->right);
q.pop();
}
v.push_back(sum*1.0/n);
}
}
vector averageOfLevels(TreeNode* root) {
BFS(root);
return v;
}
};
剑指 Offer 32 - II. 从上到下打印二叉树 II - 力扣（LeetCode）
class Solution {
public:
vector> levelOrder(TreeNode* root) {
vector>res;
if(root==nullptr)return res;
queueq;
q.push(root);
while(!q.empty()){
int n=q.size();
vectortemp;
for(int i=0;ival);
if(t->left)q.push(t->left);
if(t->right)q.push(t->right);
q.pop();
}
res.push_back(temp);
}
return res;
}
};
102. 二叉树的层序遍历 - 力扣（LeetCode）
class Solution {
public:
vector>ans;
void BFS(TreeNode* root){
queueq;
q.push(root);
while(!q.empty()){
int n=q.size();
vectorv;
for(int i=0;ival);
if(temp->left)q.push(temp->left);
if(temp->right)q.push(temp->right);
q.pop();
}
ans.push_back(v);
}
}
vector> levelOrder(TreeNode* root) {
if(root==nullptr)return {};
BFS(root);
return ans;
}
};
3.双树相关 101. 对称二叉树 - 力扣（LeetCode） 剑指 Offer 28. 对称的二叉树 - 力扣（LeetCode）
class Solution {
public:
bool check(TreeNode* x,TreeNode* y){
if(x==nullptr && y==nullptr)return true;
if(x==nullptr || y==nullptr)return false;
return x->val==y->val && check(x->left,y->right) && check(x->right,y->left);
}
bool isSymmetric(TreeNode* root) {
return check(root,root);
}
};
617. 合并二叉树 - 力扣（LeetCode）
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1==nullptr)return root2;
if(root2==nullptr)return root1;
auto newNode=new TreeNode(root1->val+root2->val);
newNode->left=mergeTrees(root1->left,root2->left);
newNode->right=mergeTrees(root1->right,root2->right);
return newNode;
}
};
100. 相同的树 - 力扣（LeetCode）
剑指 Offer 27. 二叉树的镜像 - 力扣（LeetCode）
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);
}
};
572. 另一棵树的子树 - 力扣（LeetCode）
class Solution {
public:
bool judge(TreeNode* root1,TreeNode* root2){
if(root1==nullptr && root2==nullptr)return true;
if(root1==nullptr || root2==nullptr)return false;
return root1->val==root2->val && judge(root1->left,root2->left) && judge(root1->right,root2->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(root==nullptr || subRoot==nullptr)return false;
return judge(root,subRoot) || isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}
};
235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if((root->val-q->val) * (root->val-p->val)<=0){
return root;
}
return lowestCommonAncestor(p->valval?root->left:root->right,p,q);
}
};
236. 二叉树的最近公共祖先 - 力扣（LeetCode）
剑指 Offer 68 - II. 二叉树的最近公共祖先 - 力扣（LeetCode）
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==nullptr)return root;
if(root==p || root==q)return root;
TreeNode* L=lowestCommonAncestor(root->left,p,q);
TreeNode* R=lowestCommonAncestor(root->right,p,q);
if(L==nullptr)return R;
if(R==nullptr)return L;
if(L && R)return root;
return nullptr;
}
};
4.树的深度、AVL相关、树的路径
110. 平衡二叉树 - 力扣（LeetCode）
剑指 Offer 55 - II. 平衡二叉树 - 力扣（LeetCode）
class Solution {
public:
int getHeight(TreeNode* root){
if(root==nullptr)return 0;
return max(getHeight(root->left),getHeight(root->right))+1;
}
bool isBalanced(TreeNode* root) {
if(root==nullptr)return true;
return abs( getHeight(root->left) - getHeight(root->right) )<=1 &&
isBalanced(root->left) && isBalanced(root->right);
}
};
111. 二叉树的最小深度 - 力扣（LeetCode）
class Solution {
public:
int MIN=INT_MAX;
void DFS(TreeNode* root,int currentDep){
if(root==nullptr){
return;
}
if(root->left==nullptr && root->right==nullptr){
MIN=min(MIN,currentDep);
return;
}
DFS(root->left,currentDep+1);
DFS(root->right,currentDep+1);
}
int minDepth(TreeNode* root) {
if(root==nullptr)return 0;
DFS(root,1);
return MIN;
}
};
104. 二叉树的最大深度 - 力扣（LeetCode）
class Solution {
public:
int currentDepth=0;
int maxDep=INT_MIN;
void DFS(TreeNode* root){
if(root==nullptr){
return ;
}
currentDepth++;
maxDep=max(maxDep,currentDepth);
DFS(root->left);
DFS(root->right);
currentDepth--;
}
int maxDepth(TreeNode* root) {
if(root==nullptr)return 0;
DFS(root);
return maxDep;
}
};
112. 路径总和 - 力扣（LeetCode）
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);
}
};
257. 二叉树的所有路径 - 力扣（LeetCode）
class Solution {
public:
void DFS(TreeNode*root,string s,vector&ans){
if(root){
s+=to_string(root->val);
if(root->left==nullptr && root->right==nullptr){
ans.push_back(s);
}else{
s+="->";
DFS(root->left,s,ans);
DFS(root->right,s,ans);
}
}
}
vector binaryTreePaths(TreeNode* root) {
vectorv;
DFS(root,"",v);
return v;
}
};
543. 二叉树的直径 - 力扣（LeetCode）
class Solution {
public:
int ans=1;
int deep(TreeNode* root){
if(root==nullptr){
return 0;
}
int L=deep(root->left);
int R=deep(root->right);
ans=max(ans,L+R+1);//题目中所谓的直径
return max(L,R)+1;//子树的深度
}
int diameterOfBinaryTree(TreeNode* root) {
if(root==nullptr)return 0;
deep(root);
return ans-1;
}
};
剑指 Offer 55 - I. 二叉树的深度 - 力扣（LeetCode）
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==nullptr)return 0;
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};
5.树的一些trick操作 226. 翻转二叉树 - 力扣（LeetCode）
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root==nullptr){
return nullptr;
}
swap(root->left,root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};
404. 左叶子之和 - 力扣（LeetCode）
class Solution {
public:
int sum=0;
void DFS(TreeNode* root){
if(root==nullptr)return;
if(root->left){
if(root->left->left==nullptr && root->left->right==nullptr){
sum+=root->left->val;
}
DFS(root->left);
}
DFS(root->right);
}
int sumOfLeftLeaves(TreeNode* root) {
if(root==nullptr)return 0;
DFS(root);
return sum;
}
};
6.二叉搜索树BST
利用好BST的中序遍历是一个有序序列的特征，由此可利用二分操作，不论是从小到大还是从大到小。
108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode） 面试题 04.02. 最小高度树 - 力扣（LeetCode）class Solution {
public:
TreeNode* helper(vector& nums,int left,int right){
if(left>right){
return nullptr;
}
int mid=(left+right)>>1;
TreeNode* newNode=new TreeNode(nums[mid]);
newNode->left=helper(nums,left,mid-1);
newNode->right=helper(nums,mid+1,right);
return newNode;
}
TreeNode* sortedArrayToBST(vector& nums) {
return helper(nums,0,nums.size()-1);
}
};
501. 二叉搜索树中的众数 - 力扣（LeetCode）
class Solution {
public:
TreeNode* pre=nullptr;
vectorans;
int cnt=0;
int maxCount=INT_MIN;
void DFS(TreeNode* root){
if(root==nullptr)return;
DFS(root->left);
if(pre==nullptr){
cnt=1;
}else if(pre->val==root->val){
cnt++;
}else{
cnt=1;
}
pre=root;
if(cnt==maxCount){
ans.push_back(root->val);
}
if(cnt>maxCount){
maxCount=cnt;
ans.clear();
ans.push_back(root->val);
}
DFS(root->right);
}
vector findMode(TreeNode* root) {
DFS(root);
return ans;
}
};
653. 两数之和 IV - 输入 BST - 力扣（LeetCode）
class Solution {
public:
unordered_setm;
bool findTarget(TreeNode* root, int k) {
if(root==nullptr)return false;
if(m.count(k-root->val)==1){
return true;
}
m.insert(root->val);
return findTarget(root->left,k) || findTarget(root->right, k);
}
};
700. 二叉搜索树中的搜索 - 力扣（LeetCode）
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if(root==nullptr)return nullptr;
if(val==root->val){
return root;
}
return valval?searchBST(root->left, val):searchBST(root->right,val);
}
};
剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣（LeetCode）
class Solution {
public:
int ans;
void InOrder(TreeNode* root,int &k){
if(root==nullptr)return;
InOrder(root->right,k);
--k;
if(k==0)ans=root->val;
InOrder(root->left,k);
}
int kthLargest(TreeNode* root, int k) {
if(root==nullptr)return 0;
InOrder(root,k);
return ans;
}
};
7.优先队列（TopK，堆排序） 703. 数据流中的第 K 大元素 - 力扣（LeetCode）
class KthLargest {
public:
int k;
priority_queue,greater>q;
KthLargest(int k, vector& nums) {
this->k=k;
for(auto &i:nums){
add(i);
}
}
int add(int val) {
q.push(val);
if(q.size()>k){
q.pop();
}
return q.top();
}
};
