题型：二叉树
力扣94题 二叉树的中序遍历
class Solution {
public:
void traversal(TreeNode *cur,vector<int>&vec){
if(cur==nullptr) return;
traversal(cur->left,vec);
vec.push_back(cur->val);
traversal(cur->right,vec);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int>result;
traversal(root,result);
return result;
}
};
力扣102题 二叉树的层序遍历
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*>que;
if(root!=nullptr) que.push(root);
vector<vector<int>>result;
while(!que.empty()){
int size = que.size();
vector<int>vec;
for(int i=0;i<size;i++){
TreeNode *node = que.front();
que.pop();
vec.push_back(node->val);
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
};
力扣226题 翻转二叉树
递归三部曲
1.确定递归函数的参数和返回值
TreeNode *invertTree(TreeNode* root)
2.确定终止条件
if(root==nullptr) return root;
3.确定单层递归的逻辑
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root==nullptr){
return nullptr;
}
TreeNode *left = invertTree(root->left);
TreeNode *right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
};
力扣101题 对称二叉树
1.确定递归函数的参数和返回值
比较的是根节点的两个子树是否是相互翻转的，从而判断这个树是不是对称树，所以要比较的是两棵树
返回值是bool类型
bool compare(TreeNode *left,TreeNode *right)
2.确定终止条件
节点为空的情况有：
左节点为空，右节点不为空，不对称，return false
左不为空，右为空，不对称，return false
左右不为空，对称，返回true
3.左右都不为空，比较节点数值，不相同就return false。
if(left==nullptr && right !=nullptr) return false;
else if(left!=nullptr && right==nullptr) return false;
else if(left==nullptr && right==nullptr) return true;
else if(left->val!=right->val) return false;
3.确定单层递归的逻辑
（1）比较二叉树外侧是否堆成：传入的是左节点的左孩子，右节点的右孩子
（2）比较内侧是否对称，传入左节点的右孩子，右节点的左孩子
（3）如果左右都对称就返回true，有一侧不对称就返回false。
bool outside = compare(left->left,right->right);
bool inside = compare(left->right,right->left);
bool isSame = outside && inside;
return isSame;
class Solution {
public:
bool compare(TreeNode *left,TreeNode *right){
if(left==nullptr && right !=nullptr) return false;
else if(left!=nullptr && right==nullptr) return false;
else if(left==nullptr && right==nullptr) return true;
else if(left->val!=right->val) return false;
bool outside = compare(left->left,right->right);
bool inside = compare(left->right,right->left);
bool isSame = outside && inside;
return isSame;
}
bool isSymmetric(TreeNode* root) {
if(root==nullptr) return true;
return compare(root->left,root->right);
}
};
力扣 104题 二叉树的最大深度
先用后序遍历（左右中）来计算树的高度
1.确定递归函数的参数和返回值
int getdepth(TreeNode *node)
2.确定终止条件：如果为空节点的话，就返回0，表示高度为0
if(node==NULL) return 0;
3.确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值再+1就是目前节点为根节点的树的深度。
int leftdepth = getdepth(node->left);
int rightdepth = getdepth(node->right);
int depth = 1+max(leftdepth,rightdepth);
return depth;
class Solution {
public:
int getdepth(TreeNode *node){
if(node==nullptr) return 0;
int leftdepth = getdepth(node->left);
int rightdepth = getdepth(node->right);
int depth = 1+max(leftdepth,rightdepth);
return depth;
}
int maxDepth(TreeNode* root) {
return getdepth(root);
}
};
力扣 617题 合并二叉树
一定要定义一个结点，然后再使用递归合并。思路和求最大深度有关系
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1==nullptr){
return root2;
}
if(root2==nullptr){
return root1;
}
TreeNode *root = new TreeNode(0);
root->val = root1->val+root2->val;
root->left = mergeTrees(root1->left,root2->left);
root->right = mergeTrees(root1->right,root2->right);
return root;
}
};
力扣543题 二叉树的直径
遍历整个二叉树，求出每个节点的直径即左右子树深度相加，然后求出所有直径的最大值，因为节点本身是父节点的子树，所以返回值是当前节点的深度。
class Solution {
public:
int maxDepth(TreeNode *root,int &ans){
if(!root) return 0;
int left = maxDepth(root->left,ans);
int right = maxDepth(root->right,ans);
ans = max(ans,left+right);
return max(left,right)+1;
}
int diameterOfBinaryTree(TreeNode* root) {
int ans = 0;
maxDepth(root,ans);
return ans;
}
};
力扣98题 验证二叉搜索树
通过中序遍历下二叉树的搜索节点的数值判断有序序列
判断一个序列是否是有序的。
class Solution {
public:
vector<int>vec;
void traversal(TreeNode *root){
if(root==nullptr){
return;
}
traversal(root->left);
vec.push_back(root->val);
traversal(root->right);
}
bool isValidBST(TreeNode* root) {
vec.clear();
traversal(root);
for(int i=1;i<vec.size();i++){
if(vec[i-1]>=vec[i]) return false;
}
return true;
}
};
力扣 105题 从前序与中序遍历序列构造二叉树
力扣 114题 二叉树展开链表
力扣 124题 二叉树中最大路径和
递归计算左子节点的最大贡献值，只有在最大贡献值>0时，才会被选取
//当前节点的最大路径和 = 该节点的值+该节点的左右子节点的最大贡献值
//返回节点的最大贡献值（节点值+其子节点中的最大贡献值）
class Solution {
public:
int maxSum = INT_MIN;
int maxGain(TreeNode *node){
if(!node){
return 0;
}
int leftGain = max(maxGain(node->left),0);
int rightGain = max(maxGain(node->right,0);
int priceNewpath = node->val + leftGain+rightGain;
maxSum = max(maxSum,priceNewpath);
return node->val + leftGain + rightGain;
}
int maxPathSum(TreeNode* root) {
maxGain(root);
return maxSum;
}
};
力扣 208题 实现前缀树（考得不多，不必深究）
class TrieNode {
public:
vector<TrieNode*> children;
bool isWord;
TrieNode() : isWord(false), children(26, nullptr) {
}
~TrieNode() {
for (auto& c : children)
delete c;
}
};
class Trie {
public:
/** Initialize your data structure here. */
Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
void insert(string word) {
TrieNode* p = root;
for (char a : word) {
int i = a - 'a';
if (!p->children[i])
p->children[i] = new TrieNode();
p = p->children[i];
}
p->isWord = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
TrieNode* p = root;
for (char a : word) {
int i = a - 'a';
if (!p->children[i])
return false;
p = p->children[i];
}
return p->isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
TrieNode* p = root;
for (char a : prefix) {
int i = a - 'a';
if (!p->children[i])
return false;
p = p->children[i];
}
return true;
}
private:
TrieNode* root;
};
力扣 236题 二叉树的最近公共祖先
力扣 538题 把二叉搜索树转换为累加树