捋一遍Leetcode【hot100】的二叉树专题

二叉树专题

除了后面两个，都挺简单

二叉树的中序遍历

/*** 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>ans;void inorder(TreeNode* root){if(root==nullptr){return ;}inorder(root->left);int v = root->val;ans.push_back(v);inorder(root->right);}vector<int> inorderTraversal(TreeNode* root) {inorder(root);return ans;}
};

二叉树的最大深度

/*** 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) {if(root==nullptr){return 0;}int ll=maxDepth(root->left);int rr=maxDepth(root->right);return max(ll,rr)+1;}
};

翻转二叉树

/*** 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->left==nullptr&&root->right==nullptr){return nullptr;}TreeNode* temp=nullptr;temp=root->left;root->left=root->right;root->right=temp;TreeNode(root->left);TreeNode(root->right);}
};

对称二叉树

/*** 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> a; // a[100005];vector<int> b; //  int b[100005];void dfs1(TreeNode* root) {if (root == nullptr) {a.push_back(1000);return;}a.push_back(root->val);dfs1(root->left);dfs1(root->right);}void dfs2(TreeNode* root) {if (root == nullptr) {return b.push_back(1000);}b.push_back(root->val);dfs2(root->right);dfs2(root->left);}bool isSymmetric(TreeNode* root) {dfs1(root);dfs2(root);if (a.size() != b.size()) {return 0;}//cout<<a.size();for (int i = 0; i < a.size(); i++) {cout << a[i] << "  " << b[i] << endl;}for (int i = 0; i < a.size(); i++) {if (a[i] != b[i])return 0;}return 1;}
};

二叉树的直径

/*** 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, 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;}
};

二叉树层序遍历【有个for的bug自己看了好久】

/*** 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) {if (root == nullptr)return {};vector<vector<int>> ans;queue<TreeNode*> q;q.push(root);while (q.size()) {vector<int> vals;// auto x=q.front();int size = q.size(); //!!!!!!!for(int i=0;i<size;i++){// for (int n = q.size(); n--;) {auto node = q.front();q.pop();vals.push_back(node->val);if (node->left)q.push(node->left);if (node->right)q.push(node->right);}// for (int n = q.size(); n--;) {//     auto node = q.front();//     q.pop();//     vals.push_back(node->val);//     if (node->left)//         q.push(node->left);//     if (node->right)//         q.push(node->right);// }ans.emplace_back(vals);}return ans;}
};

        int size = q.size();for(int i=0;i<size;i++){    这个地方size一定得先计算出来，要不然会有错误！！size值就会在遍历中发生变化

将有序数组转换为二叉搜索树

/*** 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* sortedArrayToBST(vector<int>& nums) {}
};

验证二叉搜索树

/*** 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 isValidBST(TreeNode* root) {if(root==nullptr){return 1;}int p=root->val;if(root->left){int lv=root->left->val;if(lv>=p)return 0;}if(root->right){int rv=root->right->val;if(rv<=p)return 0;}return isValidBST(root->left) && isValidBST(root->right);}
};

230. 二叉搜索树中第 K 小的元素

/*** 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>v;void dfs(TreeNode* root){if(root==nullptr){return ;}dfs(root->left);v.push_back(root->val);dfs(root->right);}int kthSmallest(TreeNode* root, int k) {dfs(root);return v[k-1];}
};

二叉树的右视图

/*** 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:void bfs(TreeNode* root) {if (root == nullptr)return;queue<TreeNode*> q;q.push(root);while (q.size()) {int size = q.size();for (int i = 0; i < size; i++) {auto x = q.front();if(i==size-1) {ans.push_back(x->val);}q.pop();if (x->left)q.push(x->left);if (x->right)q.push(x->right);}}}vector<int> ans;vector<int> rightSideView(TreeNode* root) {bfs(root);return ans;}
};

114. 二叉树展开为链表

/*** 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<TreeNode*>v;void dfs(TreeNode* root){if(root==nullptr){return ;}v.push_back(root);dfs(root->left);dfs(root->right);}void flatten(TreeNode* root) {dfs(root);TreeNode* ans =root;for(int i=1;i<v.size();i++){TreeNode* p=v[i];ans->left=nullptr;ans->right=p;ans=p;}return ;}
};

从前序与中序遍历序列构造二叉树

/*** 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* buildTree(vector<int>& preorder, vector<int>& inorder) {if (preorder.empty()) { // 空节点return nullptr;}int left_size = ranges::find(inorder, preorder[0]) -inorder.begin(); // 左子树的大小vector<int> pre1(preorder.begin() + 1,preorder.begin() + 1 + left_size);vector<int> pre2(preorder.begin() + 1 + left_size, preorder.end());vector<int> in1(inorder.begin(), inorder.begin() + left_size);vector<int> in2(inorder.begin() + 1 + left_size, inorder.end());TreeNode* left = buildTree(pre1, in1);TreeNode* right = buildTree(pre2, in2);return new TreeNode(preorder[0], left, right);}
};

路径总和III

/*** 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 cnt = 0;int sum=0;void dfs(TreeNode* root, int targetSum) {if (root == nullptr)return;cnt = 0;dfs2(root, root->val, targetSum);cout << cnt << endl;sum+=cnt;dfs(root->left, targetSum);dfs(root->right, targetSum);}void dfs2(TreeNode* root, int s, int targetSum) {if (s == targetSum) {cnt += 1;}int p = root->val;if (root->left) {dfs2(root->left, s + root->left->val, targetSum);}if (root->right) {dfs2(root->right, s + root->right->val, targetSum);}}int pathSum(TreeNode* root, int targetSum) {dfs(root, targetSum);return sum;}
};

后面俩不太会